Оценки времени исполнения

Оценки времени исполнения. Cимвол O().

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

Рассмотрим алгоритм вычисления значения многочлена степени n в заданной точке x.

P_n(x) = a_nxⁿ + a_n-1x^n-1 + ... + a_ixⁱ + ... + a₁x¹ + a₀

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

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

Алгоритм 2 - вынесем x-ы за скобки и перепишем многочлен в виде 
P_n(x) = a₀ + x(a₁ + x(a₂ + ... ( a_i + .. x(a_n-1 + a_nx))).

Например, 
P₃(x) = a₃x³ + a₂x² + a₁x¹ + a₀ = a₀ + x(a₁ + x(a₂ + a₃x))

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

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

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

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

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

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

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

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

При оценке за функцию берется количество операций, возрастающее быстрее всего.

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

При оценке O() константы не учитываются.

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

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

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

Основание логарифма внутри символа O() не пишется. 
Причина этого весьма проста. Пусть у нас есть O( log₂n). Но log₂n=log₃n/log₃2, а log₃2, как и любую константу, асимптотика - символ О() не учитывает. Таким образом, O( log₂n) = O( log₃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²). Здесь мы имеем дело с неточной оценкой. Разумеется, f(n) <= 50n² при n>1, однако более сильным утверждением было бы f(n) = O(n), так как для C=50 и N=1 верно f(n) <= Cn, n>N.

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

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

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

Для рассмотренных выше алгоритмов вычисления многочлена найденные оценки являются одновременно O(), Ω() и Θ().

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

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

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