2 Oснови алгоритмiзацiï
для гiршого й кращого випадкiв . Цi оцiнки , по сутi , визначають нижню й верхню межi складностi в середньому . У такому разi оцiнка , одержана для найгiршого випадку , може служити хорошою апроксимацiєю складностi в середньому .
Oсновним недолiком O-оцiнювання є його надмiрна грубiсть . Якщо алгоритм A виконує деяку задачу за 0.001∙N , тодi як для ïï розв ’ язання за допомогою алгоритму B потрiбно 1000 ∙ N , то B у мiльйон разiв швидше за A . Oднак A та B мають одну й ту саму складнiсть O ( N ).
Можна умовно роздiлити задачi на простi , якi мають полiномiальний час розв ’ язання ( наприклад , розв ’ язання системи лiнiйних алгебраïчних рiвнянь у рацiональних числах ); складнi – задачi , якi не розв ’ язуються за полiномiальний час , або алгоритм розв ’ язання за полiномiальний час не знайдений . Крiм цього , iснують принципово алгоритмiчно нерозв ’ язнi задачi . Завершимо розгляд основ теорiï складностi тезою великого ученого . Теза Колмогорова . Проблеми , якi не можуть бути розв ’ язанi без великого перебору , залишаться за межами можливостей машини на скiльки завгодно високому ступенi розвитку технiки й культури .
2.4 Завдання для самостiйноï роботи
1 . Пояснити , що таке алгоритм . 2 . Навести властивостi алгоритму . 3 . Навести класифiкацiю внутрiшнiх структур алгоритму . 4 . Що таке складнiсть задачi , алгоритму ? 5 . Навести тезу Колмогорова . 6 . Як обчислювати складнiсть задачi , алгоритму ?
40