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