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

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

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

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

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

Примеры:

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

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

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

В отличие от оценки , оценка О требует только, что бы функция 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. Оценка  (Омега)

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

 c > 0, n0 >0 : 0  c g(n)  f(n) n  n0

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

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

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

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

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

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

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

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

В качестве критериев оптимальности алгоритма выбираются временная сложность и реже емкостная сложность алгоритма

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

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

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

Порядок алгоритма - это функция, доминирующая над точным выражением временной сложности.

При оценивании порядка сложности алгоритма следует обращать внимание лишь на ту часть функции, которая имеет наибольшую степень роста.

Пример: N²+N+100 = O(N²)

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

Выделяют следующие типичные виды сложности алгоритмов.

Классы сложности алгоритмов в зависимости от функции трудоемкости
Вид f(n)	Характеристика класса алгоритмов
1	Большинство инструкций большинства функций запускается один или несколько раз. Если все инструкции программы обладают таким свойством, то время выполнения программы постоянно.
log N	Когда время выполнения программы является логарифмическим, программа становится медленнее с ростом N. Такое время выполнения обычно присуще программам, которые сводят большую задачу к набору меньших подзадач, уменьшая на каждом шаге размер задачи на некоторый постоянный фактор. Будем рассматривать время выполнения, являющееся небольшой по величине константой. Изменение основания не сильно сказывается на изменении значения логарифма: при N=1 000, log N = 3, если основание равно 10, или порядка 10, если основание равно 2; когда N=1 000 000, значения log N увеличивается в два раза. При удвоении значения параметра log N растет на постоянную величину, а удваивается лишь тогда, когда N достигает N2.
N	Когда время выполнения программы является линейным, это обычно значит, что каждый входной элемент подвергается небольшой обработке. Когда N равно миллиону, таким же и является время выполнения. Когда N удваивается, то же происходит и со временем выполнения. Эта ситуация оптимальна для алгоритма, который должен обработать N вводов (или произвести N выводов).
N log N	Время выполнения, пропорциональное N log N, возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения. Время выполнения такого алгоритма равно N log N. Когда N=1 000 000, . Когда N удваивается, тогда время выполнения более чем удваивается.
N2	Когда время выполнения алгоритма является квадратичным, он полезен для практического использования при решении относительно небольших задач. Квадратичное время выполнения обычно появляется в алгоритмах, которые обрабатывают все пары элементов данных (возможно, в цикле двойного уровня вложенности). Когда N=1 000, время выполнения равно одному миллиону. Когда N удваивается, время выполнения увеличивается вчетверо.
N3	Похожий алгоритм, который обрабатывает тройки элементов данных (возможно, в цикле тройного уровня вложенности), имеет кубическое время выполнения и практически применим лишь для малых задач. Когда N=100, время выполнения равно одному миллиону. Когда N удваивается, время выполнения увеличивается в восемь раз.
2N	Лишь несколько алгоритмов с экспоненциальным временем выполнения имеет практическое применение, хотя такие алгоритмы возникают естественным образом при попытках прямого решения задачи, например полного перебора. Когда N=20, время выполнения имеет порядок одного миллиона. Когда N удваивается, время выполнения увеличивается экспоненциально.

Класс 0 – это класс быстрых алгоритмов с постоянным временем выполнения, их функция трудоемкости O(1). Промежуточное состояние занимают алгоритмы со сложностью O(log N), которые также относят к данному классу.

Класс Р – это класс рациональных или полиномиальных алгоритмов, функция трудоемкости которых определяется полиномиально от входных параметров. Например, O(N), O(N²), O(N³).

Класс L – это класс субэкспоненциальных алгоритмов со степенью трудоемкости O(N log N).

Класс E – это класс собственно экспоненциальных алгоритмов со степенью трудоемкости O(2^N).

Класс F – это класс собственно надэкспоненциальных алгоритмов. Существуют алгоритмы с факториальной трудоемкостью, но они в основном не имеют практического применения.

Ниже приведен ряд задач полиномиальной сложности:

- задача сортировки;

- задача поиска эйлерова цикла на графе;

- поиск некоторого слова в тексте длиной n символов;

- поиск кратчайшего пути на графе;

- линейное программирование.

Задачи класса E представляют наибольшую сложность в решении. Для нахождения ответа на такую задачу необходимо выполнить fⁿ операций, причем n – размерность входных данных, а f может быть константой, полиномом или сложным фукционалом.