Определения асимптотик роста функций.
Оглавление
- Алгоритмы и структуры данных.
- Теория.
- Определения.
- Разделяй и властвуй.
- Методы оценки времени работы рекуррентных соотношений.
- Доказательство основной теоремы о рекуррентных оценках.
- Двоичная куча и сортировка с её помощью.
- Практика.
- Сравнение времени работы различных алгоритмов сортировки.
- Теория.
По мере реализации пункты оглавления будут заменяться на ссылки.
Асимптотически точная оценка
Определение. Функция $$g(n)$$ является асимптотически точной оценкой для функции $$f(n),$$ если существуют такие положительные константы $$c_1, c_2$$ и такое число $$n_0,$$ что для всех $$n \geqslant n_0$$ справедливо неравенство:
$$ 0 \leqslant c_1 g(n) \leqslant f(n) \leqslant c_2 g(n). $$
Для краткой записи асимптотически точной оценки применяют обозначение $${f(n)=\Theta (g(n)).}$$ Данная оценка является примером симметричного отношения, т.е. если $$f(n)=\Theta (g(n)),$$ то $$g(n)=\Theta (f(n)).$$
Последнее определение можно кратно записать при помощи следующей нотации:
$$ f(n) = \Theta(g(n)) \Leftrightarrow \exists n_0, c_1, c_2 >0: \forall n \geqslant n_0 \Rightarrow 0 \leqslant c_1 g(n) \leqslant f(n) \leqslant c_2 g(n). $$
Верхняя и нижняя оценка
Асимптотическая оценка включает в себя как нижнюю, так и верхнюю оценку функций, однако эти оценки также имеет смысл рассматривать отдельно.
Определение. Функция $$g(n)$$ является верхней оценкой для функции $$f(n),$$ если существуют такая положительная константа $$c$$ и такое число $$n_0,$$ что для всех $$n \geqslant n_0$$ справедливо неравенство:
$$ 0 \leqslant f(n) \leqslant c g(n). $$
Верхняя оценка обозначается как $$f(n) = O(g(n)).$$ Запишем определение верхней оценки в краткой форме:
$$ f(n) = O(g(n)) \Leftrightarrow \exists n_0, c >0: \forall n \geqslant n_0 \Rightarrow 0 \leqslant f(n) \leqslant c g(n). $$
Аналогичным образом определяется нижняя оценка.
Определение. Функция $$g(n)$$ является нижней оценкой для функции $$f(n),$$ если существуют такая положительная константа $$c$$ и такое число $$n_0,$$ что для всех $$n \geqslant n_0$$ справедливо неравенство:
$$ 0 \leqslant с g(n) \leqslant f(n). $$
В краткой форме
$$ f(n) = \Omega(g(n)) \Leftrightarrow \exists n_0, c >0: \forall n \geqslant n_0 \Rightarrow 0 \leqslant с g(n) \leqslant f(n). $$
Предельные оценки
Определение. Функция $$g(n)$$ асимптотически доминирует над функцией $$f(n)$$, если для всякого положительного $$\epsilon$$ существует такое число $$n_0,$$ что для всех $$n \geqslant n_0$$ справедливо неравенство:
$$ 0 \leqslant f(n) \leqslant \epsilon g(n). $$
Данная оценка обозначается как $$f(n) = o(g(n)).$$ Оценка $$o$$ является более сильной оценкой, чем $$O,$$ так как кроме ограниченности отношения $$f(n) / g(n)$$ оценка в малом подразумевает, что
$$ \lim\limits_{n \rightarrow +\infty} \frac{f(n)}{g(n)} = 0. $$
Для удобства доминирование функции $$f$$ над функцией $$g$$ обозначается как $${f(n)=\omega(g(n)),}$$ что равносильно $$g(n)=o(f(n)).$$
Свойства оценок
Транзитивность
Если $$f(n) = \Theta(g(n))$$ и $$g(n) = \Theta(h(n)),$$ то $$f(n)=\Theta(h(n)).$$
Если $$f(n) = O(g(n))$$ и $$g(n) = O(h(n)),$$ то $$f(n)=O(h(n)).$$
Если $$f(n) = \Omega(g(n))$$ и $$g(n) = \Omega(h(n)),$$ то $$f(n)=\Omega(h(n)).$$
Если $$f(n) = o(g(n))$$ и $$g(n) = o(h(n)),$$ то $$f(n)=o(h(n)).$$
Если $$f(n) = \omega(g(n))$$ и $$g(n) = \omega(h(n)),$$ то $$f(n)=\omega(h(n)).$$
Рефлексивность
Если $$f(n) = \Theta(g(n)),$$ то $$f(n)=O(h(n))$$ и $$f(n)=\Omega(h(n)).$$
Симметричность
Оценка $$f(n) = \Theta(g(n))$$ равносильна $$g(n)=\Theta(f(n)).$$
Обращение
Оценка $$f(n) = O(g(n))$$ равносильна $$g(n)=\Omega(f(n)).$$
Оценка $$f(n) = o(g(n))$$ равносильна $$g(n)=\omega(f(n)).$$
Примечание
На практике, во многих случаях, интерес представляет верхняя оценка, поэтому, зачастую, в литературе приводятся только $$O-\text{оценки}.$$ Однако при выборе между алгоритмами с одинаковыми верхними оценками стоит обращать внимание и на их нижние оценки. Также следует не забывать, что рассмотренные оценки выполняются только с определённого $$n_0,$$ т.е. если ваша задача оперирует малыми объёмами данных, то распространённые оценки алгоритмов могут оказаться неприменимыми. С другой стороны, в этом случае, асимптотики роста времени работы алгоритма, как правило, не оказывают существенного влияния на общее время исполнения программы.
Литература
- Т. Кормен. Алгоритмы. Построение и анализ. – М.: МЦНМО, 2001. — 36-40 c.