Нотация асимптотического роста

 

Целые книги написаны по теории алгоритмов, но нам, простым смертным, которым не хочется влезать в дебри математики, но всë же любопытно узнать, как сравнивают алгоритмы по эффективности между собой, достаточно знать, что такое асимптотические нотации в общих чертах.

Допустим, у нас есть простейший алгоритм линейного поиска (то есть алгоритм, который перебирает последовательно все элементы массива друг за другом, в ходе этого запоминает индекс того элемента, значение которого равно искомому значению, а завершает работу, когда все элементы массива пройдены. То есть для искомого значения x массива A с количеством элементов n мы вправе записать следующий алгоритм:

1) присваиваем значение «не найдено» переменной «Ответ»;

2) для каждого индекса i (от 1 до n): если A[i] = x, то присваиваем переменной «Ответ» значение i;

3) возвращаем значение переменной «Ответ».

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

Допустим,

t1 — время на выполнение шага 1 (выполняется 1 раз),

t3 — время на выполнение шага 3 (один раз),

t2 — время на проверку условия в шаге 2 (n +1 раз),

t2′ — время на инкремент в шаге 2 (выполняется n раз),

t3 — время на проверку условия A[i] = x (выполняется n раз) и

t3′ — время на присваивание переменной «Ответ» = i (выполняется от 0 до n раз в зависимости от содержимого массива, в котором ищем значение).

Итак, в худшем случае имеем:

t1 + t2*(n +1) + t2′* n + t3* n + t3′ * n + t3,

а в лучшем:

t1 + t2 * (n +1) + t2′ * n + t2A * n + t2A′ * 0 + t3.

Сгруппируем слагаемые относительно переменного фактора n (все остальные величины — константы):

(t2 + t2′ + t3) * n + (t1 + t2 + t3) в лучшем случае и

(t2 + t2′ + t3 + t3′) * n + (t1 + t2 + t3) в худшем.

В обоих случаях у нас получается многочлен типа a* n + b, где a и b — константы.

Мы видим, что при увеличении n все меньше значения будет играть b.

 

Не вдаваясь в определение асимптотической нотации, просто покажем, что это такое. У функции, зависящей от количества шагов алгоритма, приведенной к виду многочлена, убираем все младшие члены и коэффициент при старшем члене. То есть a* n + b превращается просто в n. Это называется тета (θ) функцией или нотацией. У нас и в лучшем, и в худшем случае тета будет зависеть только от n: θ (n).

Вообще асимптотическая нотация для «худшего» случая называется

O -нотацией, а для «лучшего» случая — омега (Ω)-нотацией. В нашем случае они совпадают. То есть при O -нотации O (n) мы показываем, что время выполнения алгоритма не может быть больше, чем n, помноженный на коэффициент. Младшими членами, как уже показано, при увеличении количества шагов алгоритма мы можем пренебречь. Например, если у нас функция, описывающая быстродействие алгоритма, вроде такой: t1 * n ² + t2* n + t3, то тета-нотация будет такой: θ (n ²).

 

В целом, алгоритм с O (1) лучше, чем O (n), который лучше, чем алгоритм с O (n *log n) и т.д.

 

При сравнении конкретных алгоритмов надо помнить, что при малых значениях n нет смысла использовать эти нотации для сравнения, потому что в этом случае младшие члены многочленов могут быть даже больше, чем старшие. Однако обычно алгоритмы все же используются для обработки больших объемов данных, и именно тогда имеет значение их эффективность.

 

Итак, мы показали, что для сравнения быстродействия алгоритмов придуманы асимптотические нотации: о, омега и тета.

1.   «О большое» — верхняя граница, в то время как «Омега большое» — нижняя граница. Тета требует как «О большого», так и «Омега большого», поэтому она является точной оценкой (она должна быть ограничена как сверху, так и снизу). К примеру, алгоритм, требующий Ω(n log n) требует не менее n log n времени, но верхняя граница не известна. Алгоритм, требующий Θ(n log n), предпочтительнее, потому, что он требует не менее n log n(Ω (n log n)) и не более чем n log n (O(n logn)).

2.   f(x)=Θ(g(n)) означает, что f растет так же, как и g, когда n стремится к бесконечности. Другими словами, скорость роста f(x) асимптотически пропорциональна скорости роста g(n).

3.   f(x)=O(g(n)). Здесь темпы роста не быстрее, чем g(n). «O большое» является наиболее полезной характеристикой, поскольку представляет наихудший случай.

 

Эти обозначения в лаконичном виде представлены в таблице:

 

 

В следующей таблице представлены и другие подобные обозначения.