Обчислювальна складність алгоритму

Обчислювальна складність алгоритму, звана ще тимчасової складністю, є однією з найважливіших характеристик алгоритму, яка визначає витрати машинного часу на його реалізацію.

Обчислювальною складністю алгоритму (або просто складністю) назвемо кількість кроків виконуваних алгоритмом в гіршому випадку. Вона є функцією від розмірності задачі, представленої вхідними даними. Наприклад, для графа, що задається списками инцидентности, розмірність завдання представляється як пара (n, m). Складність алгоритму визначається, як функція f, така, що f (n, m) дорівнює числу кроків алгоритму для довільного графа з n вершинами і m ребрами.

Під кроком алгоритму розуміється машинна команда, і при такому визначенні кроку обчислювальна складність залежить від конкретної системи команд і способу трансляції. Нас же буде в подальшому цікавити не точна складність алгоритму, обчислення якої практично неможливо, а асимптотична складність, яка визначається швидкістю росту числа кроків алгоритму при необмеженому збільшенні розмірності задачі. Крім того, обчислювальна складність алгоритму, певна при різних системах команд або способах трансляції, відрізняються один від одного в p разів, де p - речова константа, а їх швидкість росту однакова.

Для порівняння швидкості росту двох функцій і будемо використовувати позначення або. Будемо говорити, що функція має порядок зростання не більше. ніж функція, що позначається, тоді і тільки тоді, коли існують С = const і N> 0 такі, що

Будемо говорити, що функція має порядок зростання не менше. ніж функція, що позначається, тоді і тільки тоді, коли існують С = const і N> 0, такі, що

Наприклад, для функції

в силу прийнятих позначень, можна записати, що або. У загальному випадку, якщо - многочлен ступеня k, то

Безпосередньо з визначення випливають такі властивості: