Асимптотические оценки онлайн. Асимптотически точная оценка функции роста. Асимптотическая оценка алгоритма

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

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

Основные оценки роста, встречающиеся в асимптотическом анализе:

Ο (О-большое) – верхняя асимптотическая оценка роста временной функции;
Ω (Омега) – нижняя асимптотическая оценка роста временной функции;
Θ (Тета) – нижняя и верхняя асимптотические оценки роста временной функции.

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

Например, время уборки помещения линейно зависит от площади этого самого помещения (Θ(S )), т. е. с ростом площади в n раз, время уборки увеличиться также в n раз. Поиск имени в телефонной книге потребует линейного времени Ο (n ), если воспользоваться алгоритмом линейного поиска, либо времени, логарифмически зависящего от числа записей (Ο (log 2 (n ))), в случае применения двоичного поиска.

Для нас наибольший интерес представляет Ο -функция. Кроме того, в последующих главах, сложность алгоритмов будет даваться только для верхней асимптотической границы.

Под фразой «сложность алгоритма есть Ο (f (n ))» подразумевается, что с увеличением объема входных данных n , время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f (n ).

Важные правила асимптотического анализа:

O (k *f ) = O (f ) – постоянный множитель k (константа) отбрасывается, поскольку с ростом объема данных, его смысл теряется, например:

O(9,1n) = O(n)

O (f *g ) = O (f )*O (g ) – оценка сложности произведения двух функций равна произведению их сложностей, например:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2)

O (f /g )=O (f )/O (g ) – оценка сложности частного двух функций равна частному их сложностей, например:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

O (f +g ) равна доминанте O (f ) и O (g ) – оценка сложности суммы функций определяется как оценка сложности доминанты первого и второго слагаемых, например:

O(n 5 +n 10) = O(n 10)

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

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

Если для функции T (n ) найдутся константы c 1 > 0 и c 2 > 0 и такое число n 0 > 0, что выполнится условие , то говорят что время выполнения алгоритма (программы) асимптотически точно соответствует функции n 2 . Этот факт обозначается как , где n – длина входа алгоритма.

Определение 1. Вообще, если и положительно определенные функции, то запись означает, что найдутся константы c 1 > 0 и c 2 > 0 и такое n 0 > 0, что для всех .

(Запись « » читается как «эф от эн есть тэта от же от эн»).

Если , то говорят, что является асимптотически точной оценкой (asymptotically tight bound) для . На самом деле это отношение симметрично, если: , то .

Рис. 2. Иллюстрация к определению

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

Проиллюстрируем свойство симметрии функции . Можно показать, что . Согласно определению надо указать положительные константы с 1 , с 2 и число n 0 так, чтобы неравенства

выполнялись для всех . Разделим все части неравенства на n 2 :

Видно, что для выполнения второго неравенства достаточно положить c 2 = 1/2. Первое будет выполнено, если (например) n 0 = 7 и c 1 =1/14.

Покажем, что В самом деле, пусть найдутся такие c 2 и n 0 , что для всех . Но тогда для всех , из чего следует что c 2 не может является константой, так как растет с увеличением n , что противоречит определению.

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

Асимптотические обозначения часто употребляются внутри формул. Например, рекуррентное соотношение вида

означает, что время выполнения алгоритма для входа длины n определяется временем выполнения для входной последовательности из (n –1) элементов и некоторой функции, про которую нам важно знать лишь, что она не меньше c 1 n и не больше c 2 n для некоторых положительных с 1 и с 2 и для всех достаточно больших n , которая по определению обозначается через . Иными словами, время работы программы при изменение входной длины увеличивается пропорционально n , а в алгоритме этому члену в выражении соответствует фрагмент с асимптотической оценкой равной n .

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

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

Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать члены меньшего порядка, которые при больших n становятся малыми по сравнению с основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет (он может повлиять только на выбор констант с 1 и с 2). Например, рассмотрим квадратичную функцию , где a, b, c – некоторые константы и a > 0. Отбрасывая члены младших порядков и коэффициент при старшем члене, находим что Чтобы убедиться в этом формально, можно положить с 1 = a/ 4, c 2 = 7a/ 4и . Вообще, для любого полинома p(n) степени d с положительным старшим коэффициентом имеем .

1.3.2 - и - обозначения

Вообще, запись включает в себя две оценки: верхнюю и нижнюю. Их можно разделить:

Определение 2. Пусть имеются функции и , которые принимают неотрицательные значения для достаточно больших значений аргумента. Говорят, что , если найдётся такая константа c > 0 и такое число n 0 , что для всех (рис. 3а).

Определение 3. Говорят, что , если найдётся такая константа c > 0 и такое число n 0 , что для всех (рис. 3б). Эти записи читаются так: «эф от эн есть о большое от же от эн», «эф от эн есть омега большая от же от эн».

Теорема 1.Для любых двух функций и свойство выполнено тогда и только тогда, когда и .

Замечание: Для любых двух функций и свойство и равносильны.

(а) (б)
Рис. 3. Верхняя (а) и нижняя (б) асимптотические оценки функции

Асимптотические обозначения могут употребляются внутри формул. Например, мы можем написать выражение

имея в виду сумму h (1) + h (2) + … + h (n ), где h (×) – некоторая функция, для которой h (i ) = O (i ). Можно показать, что сама эта сумма как функция от n есть O(n 2).

1.3.3 и обозначения

Запись означает, что с ростом n отношение остаётся ограниченным. Если к тому же

то мы пишем (читается «эф от эн есть о малое от же от эн»). Формально говоря, , если для всякого положительного найдётся такое n 0 , что при всех . Тем самым запись предполагает, что и неотрицательны для достаточно больших n .

Пример: но

Аналогичным образом вводится обозначение: говорят, что есть («эф от эн есть омега малая от же от эн»), если для всякого положительного e найдется такое n 0 , что при всех , причем

Очевидно, равносильно

Пример: , но

Таким образом, может существовать три основных случая (существует и четвертый случай, когда предела не существует, однако он встречается довольно редко в реальной практике анализа алгоритмов):

Однако на практике строгими определениями пользуются редко. Существует более удобный метод выполнения этой оценки, основанный на мощном математическом аппарате, специально созданного для вычисления пределов отношения двух рассматриваемых функций, в частности правилом Лопиталя (L"Hopital):

и формулой Стирлинга (Stirling) для достаточно больших n :

Пример 1 . Сравните порядки роста функций f (n )=n (n – 1)/2 и g (n )=n 2 .

Решение: поскольку

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

Пример 2 . Сравните порядки роста функций и .

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

Пример 3. Сравните порядки роста функций и .

Решение: воспользовавшись формулой Стерлинга, получим:

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

Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - математически оценить время исполнения подсчетом операций.

Рассмотрим алгоритм вычисления значения многочлена степени n в заданной точке x .
P n (x) = a n x n + a n-1 x n-1 + ... + a i x i + ... + a 1 x 1 + a 0

Алгоритм 1 - для каждого слагаемого, кроме a 0 возвести x в заданную степень последовательным умножением и затем домножить на коэффициент. Затем слагаемые сложить.

Вычисление i -го слагаемого(i=1..n ) требует i умножений. Значит, всего 1 + 2 + 3 + ... + n = n(n+1)/2 умножений. Кроме того, требуется n+1 сложение. Всего n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1 операций.

Алгоритм 2 - вынесем x -ы за скобки и перепишем многочлен в виде
P n (x) = a 0 + x(a 1 + x(a 2 + ... (a i + .. x(a n-1 + a n x))) .

Например,
P 3 (x) = a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 = a 0 + x(a 1 + x(a 2 + a 3 x))

Будем вычислять выражение изнутри. Самая внутренняя скобка требует 1 умножение и 1 сложение. Ее значение используется для следующей скобки... И так, 1 умножение и 1 сложение на каждую скобку, которых.. n-1 штука. И еще после вычисления самой внешней скобки умножить на x и прибавить a 0 . Всего n умножений + n сложений = 2n операций.

Зачастую такая подробная оценка не требуется. Вместо нее приводят лишь асимптотическую скорость возрастания количества операций при увеличении n.

Функция f(n) = n 2 /2 + 3n/2 + 1 возрастает приблизительно как n 2 /2 (отбрасываем сравнительно медленно растущее слагаемое 3n/2+1 ). Константный множитель 1/2 также убираем и получаем асимптотическую оценку для алгоритма 1, которая обозначается специальным символом O(n 2) [читается как "О большое от эн квадрат"].

Это - верхняя оценка, т.е количество операций(а значит, и время работы) растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.

		*nlog n**
1	0	0	1
16	4	64	256
256	8	2,048	65,536
4,096	12	49,152	16,777,216
65,536	16	1,048,565	4,294,967,296
1,048,576	20	20,969,520	1,099,301,922,576
16,775,616	24	402,614,784	281,421,292,179,456

Если считать, что числа в таблице соответствуют микросекундам, то для задачи с n=1048576 элементами алгоритму с временем работы O(log n) потребуется 20 микросекунд, алгоритму со временем O(n) - 17 минут, а алгоритму с временем работы O(n 2) - более 12 дней... Теперь преимущество алгоритма 2 с оценкой O(n) перед алгоритмом 1 достаточно очевидно.

Наилучшей является оценка O(1) ... В этом случае время вообще не зависит от n , т.е постоянно при любом количестве элементов.

Таким образом, O() - "урезанная" оценка времени работы алгоритма, которую зачастую гораздо проще получить, чем точную формулу для количества операций.

Итак, сформулируем два правила формирования оценки O().

При оценке за функцию берется количество операций, возрастающее быстрее всего.
То есть, если в программе одна функция, например, умножение, выполняется O(n) раз, а сложение - O(n 2) раз, то общая сложность программы - O(n 2) , так как в конце концов при увеличении n более быстрые (в определенное, константное число раз) сложения станут выполнятся настолько часто, что будут влиять на быстродействие куда больше, нежели медленные, но редкие умножения. Символ O() показывает исключительно асимптотику!

При оценке O() константы не учитываются.
Пусть один алгоритм делает 2500n + 1000 операций, а другой - 2n+1. Оба они имеют оценку O(n) , так как их время выполнения растет линейно.

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

Другое следствие опускания константы - алгоритм со временем O(n 2) может работать значительно быстрее алгоритма O(n) при малых n ... За счет того, что реальное количество операций первого алгоритма может быть n 2 + 10n + 6 , а второго - 1000000n + 5 . Впрочем, второй алгоритм рано или поздно обгонит первый... n 2 растет куда быстрее 1000000n .

Основание логарифма внутри символа O() не пишется.
Причина этого весьма проста. Пусть у нас есть O(log 2 n) . Но log 2 n=log 3 n/log 3 2 , а log 3 2 , как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O(log 2 n) = O(log 3 n) .

К любому основанию мы можем перейти аналогично, а значит и писать его не имеет смысла.

Математическое толкование символа O().

Определение
O(g) - множество функций f , для которых существуют такие константы C и N , что |f(x)| <= C|g(x)| для всех x>N .
Запись f = O(g) дословно обозначает, что f принадлежит множеству O(g) . При этом обратное выражение O(g) = f не имеет смысла.

В частности, можно сказать, что f(n) = 50n принадлежит O(n 2) . Здесь мы имеем дело с неточной оценкой. Разумеется, f(n) <= 50n 2 при n>1 , однако более сильным утверждением было бы f(n) = O(n) , так как для C=50 и N=1 верно f(n) <= Cn, n>N .

Другие виды оценок.

Наряду с оценкой O(n) используется оценка Ω(n) [читается как "Омега большое от эн"]. Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция f(n) = Ω(n 2) . Это значит, что даже в самом удачном случае будет произведено не менее порядка n 2 действий.
...В то время как оценка f(n) = O(n 3) гарантирует, что в самом худшем случае действий будет порядка n 3 , не больше.

Также используется оценка Θ(n) ["Тэта от эн"], которая является гибридом O() и Ω() .
Θ(n 2) является и верхней и нижней асимптотической оценкой одновременно - всегда будет выполняться порядка n 2 операций. Оценка Θ() существует только тогда, когда O() и Ω() совпадают и равна им.

Для рассмотренных выше алгоритмов вычисления многочлена найденные оценки являются одновременно O() , Ω() и Θ() .
Если добавить к первому алгоритму проверки на x=0 в возведении в степень, то на самых удачных исходных данных(когда x=0 ) имеем порядка n проверок, 0 умножений и 1 сложение, что дает новую оценку Ω(n) вкупе со старой O(n 2) .

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

Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных, Θ() - сокращенная запись одинаковых O() и Ω() .

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

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

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

В общем виде, время выполнения любого алгоритма можно представить следующим образом:

При изучении свойств и сравнении алгоритмов можно отбросить константный множитель, поскольку при достаточно больших N именно порядок роста функции является определяющим фактором. Это легко объяснить на примере. Предположим имеется 2 альтернативных алгоритма, при этом первый имеет квадратичный порядок роста, а второй - описывается линейной функцией. Также допустим, что реализация первого алгоритма близка к оптимальной, а программа выполняется на современном компьютере. В то же время, реализация второго алгоритма далека от блестящей и выполняется на устаревшем компьютере. Такой дисбаланс внешних условий можно смоделировать при помощи разницы в константных множителях (пусть,, а). При небольших N, например, при 5 данных, время выполнения первого алгоритма будет меньшим времени второго:

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

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

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

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

O-оценка является подмножеством -оценки, ограничивающим функцию анализируемого алгоритма только сверху. Иначе говоря, О-оценка асимптотически описывает худший случай для анализируемого алгоритма. Такая оценка используется при анализе наиболее часто. Существенно реже используется-оценка, ограничивающая функцию анализируемого алгоритма снизу (лучший случай).

Среди типично встречающихся асимптотических оценок вычислительной сложности алгоритмов распространенными являются следующие функции:

линейная O(N) (время пропорционально увеличению данных);

квадратичная O(N 2);

полиномиальная сложность O(N M), в частности, кубическая O(N 3);

экспоненциальная сложность O(2 N);

факториальная сложность O(N!);

логаримфическая сложность O(log(N)) (подразумевают логарифм по основанию 2);

линейно-логарифмическая сложность O(N * log(N)) ;

константная вычислительная сложность O(1) (время не зависит от количества данных).

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

Вычислительную сложность разрабатываемых алгоритмов следует максимально ограничивать, насколько это является возможным. Соотношение между данными оценками можно ощутить, представив количество выполненных инструкций на конкретных примерах, скажем при N=5, 10, 25, 100 и 500 (положим, что константные коэффициенты одинаковы для упрощения понимания). При таком объеме данных получим следующие показатели:








	очень много	очень много
очень много	очень много	очень много

Константная вычислительная сложность является идеальным случаем, часто алгоритмов с такой сложностью для решения задач просто не существует. Логарифмическая функция также растет относительно медленно. Линейная и линейно-логарифмические функции растут с приемлемой скоростью. Остальные функции растут заметно быстрее.

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

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

Поверхностная оценка вычислительной сложности

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

Ниже приведено несколько подсказок для поверхностной оценки вычислительной сложности “”на глаз” без строгого аналитического подхода.

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

Вычислительная сложность последовательности инструкций равна максимальной сложности входящих в нее инструкций.

Если нет никаких специальных сведений о вероятности срабатывания условных переходов, то все возможные условные переходы, в том числе неявные (опущенные ветки else, default), следует считать равновероятными. Сложность каждого блока инструкций оценивается отдельно, а затем выбирается максимальная из них, что и становится результатом оценки для условной конструкции в целом.

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

Вычислительная сложность двух циклов, зависящих от N, вложенных друг в друга, скорее всего описывается квадратичной функцией. Соответственно, вложенность из 3 уровней соответствует кубической сложности.

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

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

int factorial (int _x)

if (_x < 1)

return 0;

else if (_x == 1)

return 1;

return _x * factorial(_x - 1);

Первые два разветвления основного условия являются элементарными инструкциями, их вычислительная сложность оценивается как O(1). Что же касается последней ветки, сложность описывается, так называемым, рекуррентным соотношением :

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