Θ-нотация¶

Θ-нотация (тета-нотация, нотация «большой теты») — это математическая нотация, используемая в теории алгоритмов и информатике для асимптотической оценки вычислительной сложности алгоритмов. Она описывает одновременно верхнюю и нижнюю границы времени выполнения или потребления памяти алгоритма, то есть задаёт точное асимптотическое поведение функции (в пределах постоянного множителя). Θ-нотация является одной из трёх основных нотаций Ландау наряду с O-нотацией (о-большое) и Ω-нотацией (омега-большое).

¶Определение

Формально, пусть даны две функции \( f(n) \) и \( g(n) \), определённые на множестве натуральных чисел (или действительных чисел, стремящихся к бесконечности). Говорят, что \( f(n) = \Theta(g(n)) \), если существуют положительные константы \( c_1 \), \( c_2 \) и натуральное число \( n_0 \) такие, что для всех \( n \geq n_0 \) выполняется неравенство:

\[ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n). \]

Иными словами, функция \( f(n) \) растёт с той же скоростью, что и \( g(n) \), с точностью до постоянного множителя. Это означает, что \( f(n) \) одновременно является и \( O(g(n)) \), и \( \Omega(g(n)) \).

¶Связь с другими нотациями

Θ-нотация занимает промежуточное положение между O-нотацией и Ω-нотацией:

• O-нотация (\( f(n) = O(g(n)) \)) задаёт только верхнюю границу: существует константа \( c \) и \( n_0 \) такие, что \( f(n) \leq c \cdot g(n) \) для всех \( n \geq n_0 \). Она не требует, чтобы \( f(n) \) была ограничена снизу.
• Ω-нотация (\( f(n) = \Omega(g(n)) \)) задаёт только нижнюю границу: существует константа \( c \) и \( n_0 \) такие, что \( f(n) \geq c \cdot g(n) \) для всех \( n \geq n_0 \). Она не требует верхней границы.
• Θ-нотация объединяет оба условия: \( f(n) = \Theta(g(n)) \) тогда и только тогда, когда \( f(n) = O(g(n)) \) и \( f(n) = \Omega(g(n)) \).

Таким образом, Θ-нотация даёт более точную характеристику асимптотического роста, чем O или Ω по отдельности.

¶Свойства

1. Рефлексивность: \( f(n) = \Theta(f(n)) \).
2. Симметричность: если \( f(n) = \Theta(g(n)) \), то \( g(n) = \Theta(f(n)) \).
3. Транзитивность: если \( f(n) = \Theta(g(n)) \) и \( g(n) = \Theta(h(n)) \), то \( f(n) = \Theta(h(n)) \).
4. Сумма: если \( f(n) = \Theta(g(n)) \) и \( h(n) = \Theta(g(n)) \), то \( f(n) + h(n) = \Theta(g(n)) \).
5. Произведение: если \( f(n) = \Theta(g(n)) \) и \( h(n) = \Theta(k(n)) \), то \( f(n) \cdot h(n) = \Theta(g(n) \cdot k(n)) \).

Эти свойства позволяют упрощать сложные выражения, заменяя их эквивалентными асимптотическими оценками.

¶Примеры

¶Пример 1: Полиномиальная функция

Рассмотрим функцию \( f(n) = 3n^2 + 5n + 2 \). Для больших \( n \) доминирующим членом является \( n^2 \). Можно показать, что \( f(n) = \Theta(n^2) \). Действительно, выберем \( c_1 = 3 \), \( c_2 = 4 \) и \( n_0 = 1 \). Тогда для всех \( n \geq 1 \):

\[ 3n^2 \leq 3n^2 + 5n + 2 \leq 4n^2. \]

¶Пример 2: Логарифмическая функция

Функция \( f(n) = \log_2 n \) является \( \Theta(\log n) \). При этом основание логарифма не влияет на асимптотическую оценку, так как \( \log_a n = \frac{\log_b n}{\log_b a} \), и константа \( 1/\log_b a \) поглощается постоянным множителем.

¶Пример 3: Экспоненциальная функция

Функция \( f(n) = 2^n + n^3 \) является \( \Theta(2^n) \), так как экспоненциальный рост доминирует над полиномиальным.

¶Пример 4: Функция, не имеющая Θ-оценки

Функция \( f(n) = n^2 \) при чётных \( n \) и \( f(n) = n \) при нечётных \( n \) не имеет Θ-оценки, так как её рост не может быть ограничен одной функцией \( g(n) \) одновременно сверху и снизу с точностью до константы. Для такой функции существуют только O- и Ω-оценки по отдельности.

¶Применение в анализе алгоритмов

Θ-нотация широко используется для описания точной асимптотической сложности алгоритмов. Например:

• Сортировка пузырьком в худшем и среднем случае имеет сложность \( \Theta(n^2) \).
• Сортировка слиянием в любом случае имеет сложность \( \Theta(n \log n) \).
• Линейный поиск в худшем случае имеет сложность \( \Theta(n) \), а в лучшем — \( \Theta(1) \), поэтому для него нельзя указать единую Θ-оценку для всех входов.

При анализе алгоритмов различают три случая: лучший, средний и худший. Θ-нотация применяется, когда асимптотическое поведение одинаково для всех случаев (например, для сортировки слиянием) или для конкретного случая (например, худший случай для пузырька).

¶История

Нотация была введена немецким математиком Эдмундом Ландау в начале XX века для обозначения асимптотических оценок в теории чисел. Позднее, в 1960-х годах, её адаптировали для анализа алгоритмов Дональд Кнут и другие исследователи. Θ-нотация стала стандартным инструментом в курсах по алгоритмам и структурам данных.

¶Критика и ограничения

1. Игнорирование констант: Θ-нотация не учитывает постоянные множители, что может быть важно на практике (например, алгоритм \( \Theta(n^2) \) с константой 1 может быть быстрее алгоритма \( \Theta(n \log n) \) с константой 1000 для малых \( n \)).
2. Неприменимость для малых входов: асимптотические оценки справедливы только для достаточно больших \( n \), что может вводить в заблуждение при работе с небольшими объёмами данных.
3. Сложность точного определения: для некоторых алгоритмов (например, с рекурсией и условными переходами) точная Θ-оценка может быть трудно вычислима или отсутствовать.

¶Интересные факты

• В русскоязычной литературе Θ-нотацию иногда называют «тетой-большой» или просто «тета-нотацией».
• В некоторых контекстах (например, в теории сложности вычислений) Θ-нотацию заменяют на «точную асимптотику» или «асимптотическую эквивалентность».
• Θ-нотация является частным случаем асимптотического равенства: если предел \( \lim_{n \to \infty} \frac{f(n)}{g(n)} \) существует и положителен, то \( f(n) = \Theta(g(n)) \).