Попередня Змiст Наступна

1.1. СКЛАДНІСТЬ АЛГОРИТМІВ

Для оцінки алгоритмів існує багато критеріїв. Найбільшу увагу приділяють порядку росту, необхідного для розв'язання задачі часу та розміру пам'яті при збільшені вхідних даних. З кожною конкретною задачею пов'яжемо число, яке назвемо розміром задачі і яке б виражало міру кількості вхідних даних. Наприклад, розміром задачі множення матриць може бути найбільший розмір матриць-співмножників. Розміром задачі про графи може бути число ребер даного графа.
Час, витрачений на обчислення при виконанні алгоритму, являє собою суму часів окремих виконаних операторів. Програму, написану на мові високого рівня, можна перетворити прямим ( хоча і не простим) шляхом в програму на машинному коді заданої ЕОМ. Це в принципі дає метод оцінки часу виконання вказаної програми, але такий підхід орієнтований на конкретну ЕОМ і не дає загальної залежності часу обчислення від розмірів задачі. В області аналізу та побудови алгоритмів прийнято виражати час виконання, як і будь-яку іншу міру ефективності, з точністю до мультиплікативної константи. Це, зазвичай, робиться шляхом підрахунку лише певних ключових операцій, виконаних алгоритмом (що легко здійснити, аналізуючи версію цього алгоритму, записану на мові високого рівня). Такий підхід абсолютно правомірний при визначені нижніх оцінок часу виконання, оскільки невраховані операції можуть лише збільшити їх; однак при роботі з верхніми оцінками ми повинні впевнитись у тому, що вклад вибраних ключових операцій в сумі відрізняється не більше, ніж в константу раз від вкладу усіх операцій, виконаних алгоритмом.
Означення 1.2 Час, який витрачається алгоритмом, як функція розміру задачі, наз. часовою складністю цього алгоритму. Граничну поведінку цієї складності при збільшені розміру задачі наз. асимптотичною часовою складністю. Аналогічно, можна виділити об'ємну складність та асимптотичну об'ємну складність.
Просторова та часова складності як функції від розмірів задачі є дві фундаментальні оцінки ефективності при аналізі алгоритмів.
Кнут популяризував апарат позначень , які відрізняють верхні та нижні оцінки.
Оцінки складності.
(верхні оцінки);
(нижні оцінки);
(ефективні оцінки).
Таким чином, O(f(N)) використовується для вказання верхніх оцінок швидкості росту функцій або для вказання множини усіх функцій, які ростуть не швидше, ніж f(N). Наприклад, коли говорять, що алгоритм виконується за час O(f(N)), то це означає, що час його виконання обмежений зверху значенням O(f(N)) для всіх входів розміру n. Так як при цьому передбачається, що час виконання в найгіршому випадку також обмежений величиною O(f(N)), то це просто час виконання даного алгоритму.
W(f(N)) використовується для вказання нижніх оцінок швидкості росту функцій або для вказання множини усіх функцій, які ростуть не повільніше, ніж f(N). Аналогічний спосіб, але для нижніх оцінок. Нарешті, q (f(N)) використовується для вказання функцій того ж порядку, що і f(N);цей спосіб потрібний для опису "оптимальних" алгоритмів. Якщо алгоритм обробляє входи розміру n за час cn2, де c-деяка константа, то часова складність цього алгоритму є O(n2), для усіх n, крім скінченої ( можливо порожньої) множини, невід'ємних значень. Наприклад, запис позначає клас функцій, які мають швидкість росту не меншу за n, але не більшу за n2.
Попередня Змiст Наступна