Классификация по сложности

Обычно алгоритмы классифицируют в соответствии с их временной сложностью. Можно выделить следующие их типы:

1. Постоянный – сложность оценивается как O(1).

2. Линейный – оценка равна O(n).

3. Квадратный – O(n²)

4. Кубический, полиноминальный – O(n³),O(n^m).

5. Экспоненциальный – O(t^p(n)), t- константа, p(n) – некоторая полиномиальная функция.

6. Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.

С ростом n временная сложность может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма. Рассмотрим таблицу, в которой сравнивается время выполнения алгоритмов разных типов при n = 10⁶, при условии, что единицей времени для компьютера является микросекунда.

Тип                 Сложность                Кол-во операций      Время при 106 операций в сек.

Постоянные              O(1)                            1                                 1мкс

Линейные                 O(n)                            10⁶ 1 с

Квадратичные          O(n²)                           10¹² 11.6 дн.

Кубические               O(n³)                           10¹⁸ 32000 лет

Экспоненциальные O(2ⁿ)                          10³⁰¹⁰³⁰ в 10³⁰¹⁰⁰⁶ раз больше времени существования Вселенной