Обозначение Big-O: классы времени

Наша полученная формула n^2 является временной сложностью выполнения алгоритма.

Функция, которой требуется приблизительно n^2 единиц времени для обработки n входных данных, имеет временную сложность O(n^2).

Функция Big-O — это математический термин, который дает приблизительную оценку того, как скорость алгоритма изменяется в зависимости от размера входных данных.

Теперь у нас есть средства для классификации временной сложности по классам. Рассмотрим наиболее распространенные классы времени: постоянное, логарифмическое, линейное, полиномиальное и экспоненциальное время.

O(1) - постоянное время

Характеристика: мгновенная доставка.

Коду всегда требуется одно и то же время независимо от того, насколько велик входной набор.

График:

Пример: доступ к одному элементу в массиве n элементов является O(1) операцией.

O(log(n)) - логарифмическое время

Характеристика: чем больше данных, тем лучше.

Время, необходимое коду для обработки n элементов, увеличивается намного медленнее, чем при больших значениях n.

График:

Примеры: вставка или извлечение элементов в сбалансированное двоичное дерево или из него. Выполнение бинарного поиска в отсортированном массиве.

O(n) - линейное время

Характеристика: по одному.

Время, необходимое для обработки n элемента, растет линейно с ростом n.

График:

Примеры: перебор массива, чтение файла от начала до конца.

O(n*log(n)) - линейное время

Linearithmic — это искусственная смесь линейного и логарифмического.

Характеристика: линейно, но не совсем.

Где-то между O(n) и O(n^2). Немного напоминает плоскую O(n^2) кривую при малых значениях n и превращается в почти линейную кривую при больших значениях n.

График:

Примеры: Heapsort, сортировка слиянием, сортировка бинарным деревом.

O(n^m) - полиномиальное время

Для данного m > 0.

Характеристика: легко, быстро и практично (но при этом быстро замедляется).

Повторим, время обработки быстро растет. Для O(n^2), когда размер ввода удваивается, время выполнения увеличивается в четыре раза. Для O(n^3) двойной размер ввода означает восьмикратное время выполнения. И так далее.

Вот тут-то и появляется опасная зона. С увеличением n полиномиальные алгоритмы сразу становятся медленнее.

Тем не менее в диссертации Кобэма полиномиальные задачи рассматриваются как простые, быстрые и практичные. Это означает, что на горизонте есть более серьезные временные сложности.

Наша O(n^2) задача сверху относится к этому классу. Этот конкретный случай также называют квадратичным временем.

Важно учитывать, что O(n)также будет принадлежать к полиномиальному классу, так как n — это то же самое, что и n^1, следовательно, это полиномиальный термин, но из-за своей особой линейной природы он определяет отдельный класс.

График:

Примеры: пузырьковая сортировка (O(n^2)). Любые вложенные циклы: два вложенных цикла — O(n^2), три вложенных цикла — O(n^3), и так далее.

O(2^n) - экспоненциальное время

Характеристика: резкий взлет.

Даже при умеренных значениях n время обработки зашкаливает.

График:

Пример: знаменитая задача коммивояжера: найти кратчайший маршрут между n городами. Существуют разные подходы к этой проблеме, но ни один из них не относится к классу сложности ниже O(2^n).