Асимптотическая нотация

Одним из упрощенных видов анализа, используемых на практике, является асимптотический анализ алгоритмов. Целью асимптотического анализа является сравнение затрат времени и других ресурсов различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объёмах входных данных. Используемая в асимптотическом анализе оценка функции трудоёмкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объёма данных. В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Ниже перечислены основные оценки сложности.

1. Оценка Q (тетта)

Пусть f(n) и g(n) – положительные функции положительного аргумента, n ≥ 1 (количество объектов на входе и количество операций – положительные числа), тогда:

f(n) = Q (g(n)), если такие, что: с₁ g(n) £ f(n) £ c₂ g(n), при n > n₀

Обычно говорят, что при этом функция g(n) является асимптотически точной оценкой функции f(n), т.к. по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя.

Отметим, что из f(n) = Q (g(n)) следует, что g(n) = Q (f(n)).

Примеры:

1) f(n)=4n²+nlnN+174= Q(n²);

2) f(n)=Q(1) – запись означает, что f(n) или равна константе, не равной нулю, или f(n) ограничена константой на ¥: f(n) = 7+1/n = Q(1).

2. Оценка О (О большое)

В отличие от оценки Q, оценка О требует только, что бы функция f(n) не превышала g(n) начиная с n > n0, с точностью до постоянного множителя:

$ c > 0, n₀ > 0: 0 £ f(n) £ cg(n), "n > n0

Вообще, запись O(g(n)) обозначает класс функций, таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя, поэтому иногда говорят, что g(n) мажорирует функцию f(n).

Например, для всех функций:

f(n)=1/n, f(n)= 12, f(n)=3*n+17, f(n)=n*Ln(n), f(n)=6*n² +24*n+77

будет справедлива оценка О(n² )

Указывая оценку О есть смысл указывать наиболее «близкую» мажорирующую функцию, поскольку например для f(n)= n² справедлива оценка О(2ⁿ), однако она не имеет практического смысла.

3. Оценка W (Омега)

В отличие от оценки О, оценка W является оценкой снизу – т.е. определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя:

$ c > 0, n0 >0: 0 £ c g(n) £ f(n) "n > n0

Например, запись W(n*Ln(n)) обозначает класс функций, которые растут не медленнее, чем g(n) = n*Ln(n), в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

Асимптотическое обозначение О восходит к учебнику Бахмана по теории простых чисел (Bachman, 1892), обозначения Q, W введены Д. Кнутом- (Donald Knuth) [6].

В асимптотическом анализе алгоритмов разработаны специальные методы получения асимптотических оценок, особенно для класса рекурсивных алгоритмов. Очевидно, что Q оценка является более предпочтительной, чем оценка О. Знание асимптотики поведения функции трудоемкости алгоритма - его сложности, дает возможность делать прогнозы по выбору более рационального с точки зрения трудоемкости алгоритма для больших размерностей исходных данных.

Классический анализ алгоритмов в данном контексте связан, прежде всего, с оценкой временной сложности.

Временная сложность алгоритма – это асимптотическая оценка функции трудоемкости алгоритма для худшего случая.

Большинство алгоритмов имеют основной параметр, который в значительной степени влияет на время выполнения операций. Если же определяющих параметров несколько, то, как правило, один их них выражается как функция от остальных. Иногда используют и такой подход: рассматривают только один параметр, считая остальные константами.

Результатом анализа является асимптотическая оценка выполняемых алгоритмом операций в зависимости от длины входа, которая указывает порядок роста функции и результаты сравнения работы алгоритмов для больших данных.

При этом оценка на реальных данных отличается от асимптотической тем, что она ориентирована на конкретные длины входов и число выполняемых алгоритмом операций.