ign="justify"> = N * b біт інформації. Програма, що реалізує алгоритм для вирішення загальної проблеми складається з М машинних інструкцій з b м бітів - М b = М * b м біт інформації. Крім того, алгоритм може вимагати таких додаткових ресурсів абстрактної машини: d - пам'ять для зберігання проміжних результатів; r - пам'ять для організації обчислювального процесу (пам'ять, необхідна для реалізації рекурсивних викликів і повернень).
При вирішенні конкретної проблеми, заданої N словами пам'яті алгоритм виконує не більш, ніж кінцеве кількість В«елементарнихВ» операцій абстрактної машини в силу умови розгляду тільки фінітних алгоритмів.
Визначення 3 (2, стор 107). Трудомісткість алгоритму. Під трудомісткістю алгоритму для даного конкретного входу - Fa (N), будемо розуміти кількість В«елементарнихВ» операцій скоєних алгоритмом для вирішення конкретної проблеми в даній формальній системі. p align="justify"> Комплексний аналіз алгоритму може бути виконаний на основі комплексної оцінки ресурсів формальної системи, необхідних алгоритмом для вирішення конкретних проблем. Очевидно, що для різних областей застосування ваги ресурсів будуть різні, що призводить до наступної комплексній оцінці алгоритму:
yA = c1 * Fa (N) + c2 * M + c3 * Sd + c4 * Sr, де ci - ваги ресурсів.
При більш детальному аналізі трудомісткості алгоритму виявляється, що не завжди кількість елементарних операцій, виконуваних алгоритмом на одному вході довжини N, збігається з кількістю операцій на іншому вході такої ж довжини. Це призводить до необхідності введення спеціальних позначень, що відображають поведінку функції трудомісткості даного алгоритму на вхідних даних фіксованої довжини (6, стор 82-85). p align="justify"> Нехай D А - безліч конкретних проблем даної задачі, заданий у формальній системі. Нехай D ГЋ D А - завдання конкретної проблеми і | D | = N.
У загальному випадку існує власне підмножина безлічі D А, що включає всі конкретні проблеми, що мають потужність N:
позначимо це підмножина через DN: DN = {D ГЋ DN,: | D | = N};
позначимо потужність множини DN через MDN, тобто MDN = | DN |. p align="justify"> Тоді змістовно даний алгоритм, вирішуючи різні завдання розмірності N, виконуватиме в якомусь випадку найбільшу кількість операцій, а в якомусь випадку найменшу кількість ...
