1.2 Скорость роста функций

Анализируя алгоритм можно стараться найти точное количество выполня­емых им действий. Но в большинстве случаев достаточно оценить асимптотику роста времени работы алгоритма (это делается на основе точной оценки) при стремлении раз­мера входа к бесконечности (asymptotic efficiency). Если у одного алгоритма асимптотика роста меньше, чем у другого, то в большинстве случаев он бу­дет эффективнее для всех входов, кроме, может быть, совсем коротких.

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

1. Класс функций, растущих, по крайней мере, так же быстро, как ƒ, обозначается через Ω(ƒ) (читается как «омега большое»). Можно считать, что класс Ω(ƒ) задается указанием свой нижней границы: все функции из него растут, по крайней мере, так же быстро, как ƒ;

2. Класс функций, растущих не быстрее ƒ, обозначается O. Функция ƒ образует верхнюю границу для класса O(f) (читается как «о большое»);

3. Класс функций, растущих с той же скоростью, что и ƒ, обозначается () (читается как «тэта большое»). С формальной точки зрения этот класс представляет собой пересечение двух предыдущих классов.

Пусть время T(n) работы алгоритма на входах длины n есть (n²). Тогда найдутся такие константы c₁,c₂ > 0 и такое число n₀, что с₁n² ≤ T(n) ≤ с₂n² при всех n ≥ n₀. Проще говоря, начиная с некоторого размера входа n₀, функциональная зависимость T(n) может быть описана посредством n² с точностью до константы, при этом «вилка» или диапазон возможных значений константы, способной обеспечить полное соответствие описания оригиналу, задается при помощи c₁ и c₂. Вообще, если g(n) – некоторая функция, то запись f(n) = (g(n)) означает, что найдутся такие c₁,c₂  > 0 и такое n₀, что 0 ≤ с₁g(n) ≤ f(n) ≤ c₂g(n) для всех n ≥ n₀. Запись f(n) = (g(n)) читается так: «эф от эн есть тэта от же от эн».

Следует также упомянуть, что если f₁(n) = (g(n)) и f₂(n) = (g(n)), то отсюда не следует f₁(n) = f₂(n)!

Определение (g(n)) предполагает, что функции f(n) и g(n) асимптотически неотрицательны (asymptotically nonnegative), т.е. неотрицательны для достаточно больших значений n. Если функции f и g строго положительны, то можно исключить n₀ из определения (изменив константы c₁ и c₂ так, чтобы для малых n неравенство также выполнялось).

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

Рисунок 1.1 – Иллюстрации к определениям f(n) = (g(n)), f(n) = O(g(n)) и f(n) = (g(n))

Запись f(n) = (g(n)) включает в себя две оценки: верхнюю и нижнюю. Их можно разделить. Говорят, что f(n) = O(g(n)), если найдется такая константа c > 0 и такое число n₀, что 0 ≤ f(n) ≤ cg(n) для всех n ≥ n₀. Говорят, что f(n) = (g(n)), если найдется такая константа c > 0 и такое число n₀, что 0 ≤ cg(n) ≤ f(n) для всех n ≥ n₀. Эти записи читаются так: «эф от эн есть о большое от же от эн», «эф от эн есть есть омега большая от же от эн».