07. Асимптотические обозначения

---

ВПЕРЁД ⇒

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

⇐ НАЗАД

Асимптотическая оценка сложности вычислений

---

Асимптотические обозначения

Когда речь заходит об асимптотической оценке сложности вычислений, то неизбежно возникает вопрос: каким образом, для оценки времени работы алгоритма $T(n)$, необходимо выбирать функцию $f(s)$ такую, что $T(n)=f(r(n))$, где $r(n)$ - порядок роста функции $T(n)$. Зачастую мы только можем сделать предположение о том, что довольно точная оценка $f(s)$ для функции $T(n)$ находится где-то внутри некоторого множества $M$ оценок различной точности. То есть нет смысла искать конкретную оценку $f(s)$, при помощи которой можно было бы точно описать функцию $T(n)$. Вместо этого будет проще дать оценку тому, в каком множестве $M$ находится интересующая нас точная оценка $f(s)$ для функции $T(n)$. Для этой цели очень удобно использовать асимптотические обозначения (нотации), при помощи которых в математическом анализе даются оценки функциям различной природы:

• $T(n)\in O(r(n))$. Функция $T(n)$ расположена в множестве $O(r(n))$, которое асимптотически ограничивает эту функцию сверху некоторой другой функцией $c_1\cdot r(n)$. Вместо рассмотрения точной оценки $f(s)$ для $T(n)$ такой, что $T(n)=f(r(n))$, рассматривается множество функций $O(r(n))$ с расположенной в этом множестве функцией $T(n)$.
• $T(n)\in \Omega (r(n))$. Функция $T(n)$ расположена в множестве $\Omega (r(n))$, которое асимптотически ограничивает эту функцию снизу некоторой другой функцией $c_2\cdot r(n)$. Вместо рассмотрения точной оценки $f(s)$ для $T(n)$ такой, что $T(n)=f(r(n))$, рассматривается множество функций $\Omega (r(n))$ с расположенной в этом множестве функцией $T(n)$.
• $T(n)\in \Theta (r(n))$. Функция $T(n)$ расположена в множестве $\Theta (r(n))$, которое асимптотически ограничивает эту функцию сверху и снизу некоторыми другими функциями $c_1\cdot r(n)$ и $c_2\cdot r(n)$. Вместо рассмотрения точной оценки $f(s)$ для $T(n)$ такой, что $T(n)=f(r(n))$, рассматривается множество функций $\Theta (r(n))$ с расположенной в этом множестве функцией $T(n)$.

---

ВПЕРЁД ⇒

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

⇐ НАЗАД

Асимптотическая оценка сложности вычислений

---

Источники

• Павел Маврин “АиСД, Семестр 1, Лекция 1. Оценка времени. Сортировка слиянием”
• Big O нотация (Wiki)
• Томас Кормен “Алгоритмы. Построение и анализ”. Глава 2 “Приступаем к изучению”, параграф 2.2 “Анализ алгоритмов” (стр. 45-52).

Категория

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

Теги

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