Если каждый раз аккуратно выбирать

Если каждый раз аккуратно выбирать элемент-разделитель, то мы можем свести вероятность квадратичного (то есть 0(n2)) поведения практически к нулю; хорошо реализованная quicksort действительно обычно ведет себя как О(n log n).

Вот основные случаи:

Запись	Название времени	Пример
0(1)	Константное	Индексирование массива
0(log n)	Логарифмическое	Двоичный поиск
0(n)	Линейное	Сравнение строк
0(n log n)	n logn	Quicksort
0(n2)	Квадратичное	Простые методы сортировки
О(n3)	Кубическое	Перемножение матриц
0(2n)	Экспоненциальное	Перебор всех подмножеств

Доступ к элементу в массиве — операция, работающая за константное (О(1)) время. Алгоритм, за каждый шаг отсеивающий половину входных данных, как двоичный поиск, обычно займет время 0(log n). Сравнение двух строк длиной в n символов с помощью strcmp займет О(n).

Традиционный алгоритм перемножения двух квадратных матриц порядка п занимает О(и!), поскольку каждый элемент получается в результате перемножения и пар чисел и суммирования результатов, а всего элементов n2.

Экспоненциальное время работы алгоритма обычно является результатом перебора всех вариантов: у множества из п элементов — 2"различных подмножеств, поэтому алгоритм, которому надо пройтись по всем подмножествам, будет выполняться за время 0(2"), то есть будет экспоненциальным. Экспоненциальные алгоритмы обычно слишком долго работают, если только п не очень мало, поскольку добавление одного элемента удваивает время работы алгоритма. К сожалению, существует много задач, таких как, например, знаменитая "задача коммивояжера", для которых известны только экспоненциальные решения. Когда задача такова, часто вместо точных решений берут алгоритмы, находящие некоторое приближение к ответу.

Содержание раздела