Порядок роста

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

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

• Омега большое

Класс функций, растущих по крайней мере так же быстро, как f, мы обозначаем через Ω(f) (читается омега большое]. Функция g при- надлежит этому классу, если при всех значениях аргумента n, больших некоторого порога по, значение g(n) > сf(n) для некоторого положи- тельного числа с. Можно считать, что класс Ω(f) задается указанием свой нижней границы: все функции из него растут по крайней мере так же быстро, как f. Мы занимаемся эффективностью алгоритмов, поэтому класс Ω(f) не будет представлять для нас большого интереса: например, в Ω(n²) входят все функции, растущие быстрее, чем n², скажем n³ и 2ⁿ.

• О большое

На другом конце спектра находится класс O(f) (читается о большое). Этот класс состоит из функций, растущих не быстрее f. Функция f образует верхнюю границу для класса O(f). С формальной точки зрения функция g принадлежит классу О(f), если g(n)≤с/(n) для всех n, больших некоторого порога по, и для некоторой положительной константы с. т.е. g € O(f), если




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

• Тета большое

Через θ(f) (читается тета большое) мы обозначаем класс функций, растущих с той же скоростью, что и f. С формальной точки зрения этот класс представляет собой пересечение двух предыдущих классов, θ(f)=Ω(f) П O(f) Мы говорим, что R(n) имеет порядок роста θ(f(n)), что записывается R(n) =θ(f(n)), если существуют положительные постоянные k₁ и k₂, независимые от n, такие, что




для всякого достаточно большого n. (Другими словами, значение R(n) заключено между k₁f(n) и k₂f(n).)

Пример
Для линейно рекурсивного процесса вычисления факториала, число шагов растет пропорционально входному значению n. Таким образом, число шагов, необходимых этому процессу, растет как θ(n). Мы видели также, что требуемый объем памяти растет как θ(n). Для итеративного факториала число шагов по-прежнему θ(n), но объем памяти θ(1) — то есть константа. Древовиднорекурсивное вычисление чисел Фибоначчи требует θ( Ψⁿ) шагов и θ(n) памяти, где Ψ — золотое сечение.
Порядки роста дают всего лишь грубое описание поведения процесса. Например, процесс, которому требуется n² шагов, процесс, которому требуется 1000n² шагов и процесс, которому требуется 3n² + 10n + 17 шагов — все имеют порядок роста θ(n²). С другой стороны, порядок роста показывает, какого изменения можно ожидать в поведении процесса, когда мы меняем размер задачи. Для процесса с порядком роста θ(n) (линейного) удвоение размера задачи примерно удвоит количество используемых ресурсов. Для экспоненциального процесса каждое увеличение размера задачи на единицу будет умножать количество ресурсов на постоянный коэффициент.

Используемая литература:

1. Дж. Макконнелл - Основы современных алгоритмов.
2. http://mitpress.mit.edu/sicp/