O (FS) на алгоритм з T a (V) = O (V4). Він залежить від того, як завдання розбивається на підзадачі, наскільки це розбиття властиво самій задачі або є тільки штучним прийомом. Загальним керівним підходом тут може бути послідовність дій, зворотна аналізу алгоритмів. При аналізі за рекурсивному алгоритмом будується рівняння, яке потім вирішується. При оптимізації реалізується ланцюжок:
Формула, що задає бажану складність ->
Відповідне рівняння (одне з можливих) ->
Метод розбиття задачі на підзадачі.
Другий вид оптимізації, не змінюючи структури програми в цілому, веде до економії пам'яті та/або спрощення роботи зі структурами даних, підвищенню ефективності допоміжних процедур, що забезпечують "інтерфейс" між прикладним рівнем (на якому мислимо в термінах високорівневих об'єктів - графів, матриць, текстів і т. д.) і машинним рівнем, що підтримує найпростіші типи даних (числа, символи, покажчики). Результатом цього зазвичай є зменшення коефіцієнтів при деяких доданків у функції складності (при вдалій оптимізації - при найбільш значимому слагаемом), але порядок функції складності залишається тим же. (7, стр. 204)
Обидва види оптимізації доповнюють один одного і можуть застосовуватися спільно.
Висновок
Теорія алгоритмів - це наука, що вивчає загальні властивості та закономірності алгоритмів, різноманітні формальні моделі їх подання. На основі формалізації поняття алгоритму можливе порівняння алгоритмів по їх ефективності, перевірка їх еквівалентності, визначення областей застосовності. p align="justify"> Розроблені в 1930-х роках різноманітні формальні моделі алгоритмів (Пост, Тьюринг, Черч), так само як і запропоновані в 1950-х роках моделі Колмогорова і Маркова, виявилися еквівалентними в тому сенсі, що будь-який клас проблем , розв'язаних в одній моделі, вирішувані і в іншій.
В даний час отримані на основі теорії алгоритмів практичні рекомендації отримують все більше поширення в області проектування і розробки програмних систем.
Одне із завдань, яка зазвичай ставиться при розробці алгоритмів і програм - мінімізація необхідних програмою ресурсів. Особливо це стосується системного програмного забезпечення: програм ОС, трансляторів, систем управління базами даних і знань і т. д., тобто програм, що мають велику кількість користувачів і що зазнають як товар, велику конкуренцію на ринку програмних засобів.
Теорія складності алгоритмів пропонує достатні ефективні методи вирішення поставленої проблеми. Точне рішення можливо в переважній більшості практично важливих ситуацій. p align="justify"> Проте як і раніше відкриті питання, пов'язані зі сводимости алгоритмів один до одного і залишається невирішеною ...
