10. Асимптотическое обозначение тета-большое

---

ВПЕРЁД ⇒

Инвариант цикла (на примере задачи сортировки)

⇐ НАЗАД

Асимптотическое обозначение омега-большое

---

Асимптотические обозначение тета-большое

Для алгоритма поиска минимального элемента в массиве размерностью $n$ мы получили следующую зависимость для наихудшего и наилучшего случаев входных данных:

$T(n)=6n+3$, где $n$ - линейный порядок роста сложности вычислений алгоритма. То есть функция $T(n)$ ведёт себя линейным образом.

Также, на примере этого же алгоритма, были объяснены понятия асимптотических обозначений о-большое и омега-большое.

Таким образом, получаем:

$$\begin{array}{rl}T(n)& =6n+3=O(n);\\ T(n)& =6n+3=\Omega (n).\end{array}$$

С одной стороны, сложность алгоритма поиска минимального элемента в массиве растёт не быстрей, чем линейная зависимость $O(n)$. С другой стороны, сложность этого алгоритма растёт не медленней, чем аналогичная линейная зависимость $\Omega (n)$. Если рост сложности указанного алгоритма ограничен сверху и снизу линейными зависимостями, то мы точно можем сказать, что и сама оцениваемая функция $T(n)$ представляет собой линейную зависимость. Исходя из этого, можем сделать следующее заключение:

Если для функции $f(n)$ существует такая функция $g(n)$, что одновременно выполняются два условия $\{\begin{array}{l}f(n)=O(g(n)),тоесть0\le f(n)\le c_2\cdot g(n)\\ f(n)=\Omega (g(n)),тоестьf(n)\ge c_1\cdot g(n)\ge 0\end{array}$ , то это эквивалентно записи $f(n)=\Theta (g(n))$.

Обозначение $\Theta (...)$, применяющееся в математическом анализе для оценки любой произвольной функции, носит название $\Theta$-нотации/обозначения (нотации тета-большое; big-theta notation). В случае анализа алгоритмов, данная нотация говорит нам о том, что, с ростом размера входных данных, время работы алгоритма увеличивается не быстрей и не медленней, чем порядок роста (то есть в точности как порядок роста), указанный во входном параметре оценки (в данном примере, в точности, как порядок роста $n$). Иными словами, рассматриваемый алгоритм работает (в контексте скорости исполнения) не хуже и не лучше указанного порядка роста ($n$).

Поскольку для всех $n\ge n_0$ функция $f(n)$ равна функции $g(n)$ с точностью до постоянного множителя (то есть для функции $g$ можно подобрать такие множители, благодаря которым эта функция $g$ будет ограничивать сверху и снизу функцию $f$), то говорят, что функция $g(n)$ является асимптотически точной оценкой функции $f(n)$.

Аналогично асимптотическим оценкам о-большое и омега-большое, запись $T(n)=\Theta (g(n))$ говорит о существовании некоторого множества $\Theta (g(n))$, в котором находится функция $T(n)$.

Для заданной функции $g(n)$ запись $\Theta (g(n))$ (которая произносится как “тета-большое от $g$ от $n$”) обозначает множество функций $M=\{f_1(n),f_2(n),...,f_m(n)\}$ такое, что для всех функций из этого множества можно найти некоторые положительные константы $c_1$, $c_2$ и $n_0$ такие, что $0\le c_1\cdot g(n)\le f_k(n)\le c_2\cdot g(n)$ для всех $n\ge n_0$ и всех $k$ из $\{1,...,m\}$.

Ниже представлено определение для $\Theta$-нотации в математической символьной форме (расшифровка математической записи идёт сразу следом за самой математической записью):

Определение $\Theta$-нотации

$f(n)=\Theta (g(n))\iff \exists n_0>0,c_1>0,c_2>0:\forall n\ge n_0\Rightarrow 0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$.

Расшифровка математической записи:

Утверджение $f(n)=\Theta (g(n))$ эквивалентно (равносильно) утверждению, что существуют положительные константы $n_0$, $c_1$ и ${с}_2$ такие, что для любых значений $n$, больших или равных $n_0$, выполняется условие $0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$, то есть из выполнения условия $n\ge n_0$ следует выполнение условия $0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$,.

Обратите внимание: $\Theta (g(n))$ на самом деле представляет собой множество, содержащее в себе функцию $f(n)$, то есть можно сделать запись "$f(n)\in \Theta (g(n))$", чтобы указать на тот факт, что $f(n)$ является членом $\Theta (g(n))$.

Однако, вместо использования математически правильной записи "$f(n)\in \Theta (g(n))$", для удобства обычно используют менее точную (с математической точки зрения) запись "$f(n)=\Theta (g(n))$". Эта запись и соответствующий ей выше рисунок интуитивно воспринимаются читателем как: “Для всех значений $n$, лежащих справа от $n_0$, значения функции $f(n)$ больше или равны значениям функции $c_1\cdot g(n)$, а также меньше или равны значениям функции $c_2\cdot g(n)$“.

Возвращаясь к алгоритму поиска минимального элемента в массиве размерностью $n$ и его времени работы $T(n)=6n+3$, можем сделать очевидный вывод о существовании констант $c_1$, $c_2$ и $n_0$ таких, что будет выполняться условие $0\le c_1\cdot n\le 6n+3\le c_2\cdot n$ для $n\ge n_0$. Например, для $c_1=6$, $c_2=7$ и $n_0=3$ получаем, что $0\le 6n\le 6n+3\le 7n$ для $n\ge 3$. Это и означает, что $T(n)=\Theta (n)$.

В отличие от нотаций "$f(n)=O(g(n))$" и "$f(n)=\Omega (g(n))$", нотация "$f(n)=\Theta (g(n))$" даёт точную оценку (с точностью до множителя) исходной функции $f(n)$, то есть в оценке $\Theta (g(n))$ можно указать только один единственный порядок роста $g(n)$, в точности совпадающий с порядком роста исходной функции. Если в $\Theta (g(n))$ указать порядок роста больший, чем есть на самом деле, то рано или поздно функция $f(n)$ пересечётся с нижней границей $c_1\cdot g(n)$. И наоборот, если в $\Theta (g(n))$ указать порядок роста меньший, чем есть на самом деле, то рано или поздно функция $f(n)$ пересечётся с верхней границей $c_2\cdot g(n)$.

Замечание об асимптотической сложности постоянной (константной) функции

Если $\Theta (g(n))$ представляет собой асимптотически точную оценку некоторой функции $f(n)$, то есть для функции $f(n)$ существует только один единственный порядок роста $g(n)$, то возникает логичный вопрос:

Каким образом оценивать (выбирать порядок роста) для постоянных (константных) функций вида $f(x)=const$?

Выведем ответ на данный вопрос:

$f(n)=const=const\cdot (1)=const\cdot (n^0)=\Theta (n^0)=\Theta (1)$.

Таким образом, условимся употреблять $\Theta (1)$ для обозначения либо константы, либо постоянной функции по отношению к некоторой переменной. Допустимо также вместо $\Theta (1)$ использовать $O(1)$.

---

ВПЕРЁД ⇒

Инвариант цикла (на примере задачи сортировки)

⇐ НАЗАД

Асимптотическое обозначение омега-большое

---

Источники

• Павел Маврин “АиСД, Семестр 1, Лекция 1. Оценка времени. Сортировка слиянием”
• Big O нотация (Wiki)
• Томас Кормен “Алгоритмы. Построение и анализ”. Глава 3 “Рост функций”, параграф 3.1 “Асимптотические обозначения” (стр. 68-78).

Категория

Алгоритмы-и-структуры-данных Алгоритмы-и-структуры-данных

Теги

• Алгоритм Алгоритм
• Сложность-по-времени Сложность-по-времени
• Временная-сложность Временная-сложность
• Time-complexity Time-complexity
• Сложность-вычислений Сложность-вычислений
• Асимптотическая-оценка Асимптотическая-оценка
• Оценка-сложности-вычислений Оценка-сложности-вычислений
• Big-Theta Big-Theta