домостей для того, щоб завдання мінімізації могла бути поставлена ​​із звичайною для математики визначеністю. Цьому заважає декілька чинників. p align="justify"> По-перше, складно сформулювати критерій оптимізації, що має одночасно і безперечне практичне значення і однозначно визначений у математичному плані. Наприклад, можна поставити завдання мінімізації числа команд машини Тьюринга - критерій, добре певний математично; але зовсім неясно його практичне значення, оскільки навряд чи реальна програма на реальному комп'ютері буде моделювати машину Тьюринга. Можна поставити завдання мінімізації часу виконання програми на реальній машині - ясний з практичної точки зору критерій. Однак неможливо буде вирішити завдання оптимізації математичними методами, так як час виконання залежить (іноді значно) від архітектури ЕОМ, а архітектуру сучасних комп'ютерів не опишеш невеликим числом параметрів. Важливо також, що програма, що працює швидше інших на одному комп'ютері, може виявитися не найшвидшою на іншому. Існують навіть спеціальні програми з загальною назвою benchmark, призначені для оцінки архітектур. p align="justify"> друге, не зовсім ясно, що таке складність завдання. Її можна було б визначити як мінімальну зі складностей алгоритмів, що вирішують цю задачу. Але чи існує алгоритм мінімальної складності (як переконатися, що знайдений алгоритм дійсно мінімальний або, навпаки, не мінімальний)? Чи до чого прагнути? І наскільки важкий пошук цього мінімуму? Ці питання пов'язані з нижньою оцінкою складності алгоритмів (а не верхній, як у попередніх кроках) (5, стор 89-92). p align="justify"> Чи можна для розглянутої задачі довести, що ніякої вирішальний її алгоритм не може бути простіше цієї нижньої оцінки? Візьмемо відому задачу перемноження квадратних матриць. Наведено алгоритм складності Т a (n) = 3n3 + n2. (8, стр. 199-203) Ймовірно, це не кращий алгоритм, але яка оцінка знизу? Результуюча матриця має n2 елементів. Для обчислення будь-якого елементу потрібна хоча б одна операція однопроцесорній машини - два елементи за одну операцію знайти не можна. Для мінімального алгоритму ми отримуємо нерівності n2 <= T a , min (n) <= 3n3 + n2. Навряд чи n2 - хороша нижня оцінка, але вже відомо, що n3 нижньої оцінкою не є, так як знайдені більш швидкі алгоритми (зокрема, алгоритм Штрассена). (8, стр. 211)
Існує кілька самостійних аспектів оптимізації програм, з яких виділимо два:
- оптимізація, пов'язана з вибором методу побудови алгоритму;
- оптимізація, пов'язана з вибором методів представлення даних в програмі.
Перший вид оптимізації має глобальний характер і веде до зменшення порядку функції складності - наприклад, заміна алгоритму з Т a ( V) = ...
