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

Рассмотрим алгоритм вычисления значения многочлена степени 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) [читается как "О большое от эн квадрат"].

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

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

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

Таким образом, 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(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() и Ω() .

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

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

Асимптотическая оценка сложности обозначается греческой буквой Θ (тета).

f(n) = Θ(g(n)), если существуют c1, c2>0 и n0 такие, что c1*g(n)<=f(n)<=c2*g(n) , при n>n0.

Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n), приведенное неравенство называется асимптотическим равенством, а само обозначение Θ символизирует множество функций, которые растут “так же быстро”, как и функция g(n) – т.е. с точностью до умножения на константу. Как следует из приведенного неравенства, оценка Θ являет собой одновременно и верхнюю и нижнюю оценки сложности. Не всегда есть возможность получить оценку в таком виде, поэтому верхнюю и нижнюю оценки иногда определяют отдельно.
Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).
f(n)= Ο(g(n)), если существует c>0 и n0 такие, что 0<=f(n)<=cg(n), при n>n0.
Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).
f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0<=cg(n)<=f(n), при n>n0.
Как следствие: асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего под оценкой сложности понимают верхнюю оценку сложности. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится.

{$APPTYPE CONSOLE}

uses
SysUtils;
var n:Integer;
function result(n:integer):Integer; //ôóíêöèÿ ïîäñ÷åòà êîëè÷åñòâà äåëèòåëåé
var i:Integer;
begin
result:=0;
for i:= 2 to n div 2 do
if n mod i =0 then
result:=result+1;
end;

begin
read(n); // ââîä ÷èñëà
write(result(n));
readln;
readln;
end.
end.

4. Рекурсия с запоминанием (прозрачный вариант динамического программирования). Пример быстрого вычисления биномиальных коэффициентов по формуле C(n,m)=C(n-1,m)+C(n-1,m-1)

Есть способ решить проблему повторных вычислений. Он очевиден - нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память. Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:

создать глобальный массив FD, состоящий из нулей;

после вычисления числа F(n) поместить его значение в FD[n];

в начале рекурсивной процедуры сделать проверку на то, что FD[n] = 0 и, если, то вернуть FD[n] в качестве результата, а иначе приступить к рекурсивному вычислению F(n).

{Функция на Pascal}

function C(m, n:Byte):Longint;

If (m=0) or (m=n)

Else C:=C(m, n-1)+C(m-1, n-1)

{Процедура на Pascal}

Procedure C(m, n: Byte; Var R: Longint);

Var R1, R2: Longint;

If (m=0) or (m=n)

Для теоретического анализа принципиальна не конкретная функция, описывающая зависимость времени выполнения от количества входных данных, а порядок ее роста для больших 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). Что же касается последней ветки, сложность описывается, так называемым, рекуррентным соотношением :

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