Как в учебнике
Для достаточно больших натуральных $n$ пусть $f(n)\ge0$ и $g(n)>0$. Запись $f\in\Theta(g)$ означает, что существуют постоянные $c,C>0$ и $n_0$ с $c g(n)\le f(n)\le C g(n)$ для всех $n\ge n_0$. Это одновременно верхняя и нижняя оценки.
Для $f(n)=3n+7$ при $n\ge1$ верно $3n\le3n+7\le10n$. Поэтому $f\in\Theta(n)$. Класс включает разные постоянные множители и младшие слагаемые; принадлежность ему не утверждает, что функция равна $n$ или отношение к $n$ стремится к 1.
При фиксированном основании $b>1$ логарифмы удовлетворяют $\log_b n=\ln n/\ln b$. Поэтому $\Theta(\log_b n)=\Theta(\ln n)$: основание меняет постоянный множитель, но не порядок. Численные значения логарифмов при этом различаются.
Для алгоритма указывают размер входа, модель единичных операций, рассматриваемый случай и ресурс. Если процедура всегда проходит массив из $n$ элементов с фиксированной работой на элемент и фиксированной начальной работой, время имеет порядок $\Theta(n)$ в этой модели. О памяти из этого автоматически ничего не следует.
Две исходные оценки могут иметь разные пороги. Если верхняя работает с $n_1$, а нижняя с $n_2$, общий порог выбирают как $\max(n_1,n_2)$: после него действуют обе. Для доказательства принадлежности $\Theta(g)$ нужны именно два неравенства. Одной верхней оценки недостаточно, поскольку под тем же потолком могут находиться функции с существенно меньшим ростом.
Определения и обозначения: Mathematics for Computer Science.
Связанные понятия: O-большое: верхняя оценка роста, Ω-большое: нижняя оценка роста.
На пальцах
Точная оценка порядка зажимает функцию в коридоре между двумя постоянными кратными одного масштаба. Пол и потолок удерживают весь достаточно далёкий хвост, хотя функция может колебаться между ними. Затраты 3n и 7n относятся к одному порядку, но разницу на конкретном входе всё равно оплачивает процессор. Θ описывает масштаб коридора, а не точный маршрут: асимптотическая табличка на двери не обязана совпадать с показаниями секундомера.
Пример
Для учебной функции $3n+7$ границы зафиксированы как $3n$ и $10n$. Пример охватывает три размера входа.
Θ-большое: точный порядок роста
Малый вход
При n = 1 затраты касаются верхней границы.
Шаг 1 из 4: Малый вход
Все шаги текстом
Малый вход
При n = 1 затраты касаются верхней границы.
- Низ; затраты; верх
- 310включён10
Средний вход
При n = 10 функция остаётся внутри тех же линейных границ.
- Низ; затраты; верх
- 3037включён100
Больший вход
При n = 100 границы по-прежнему используют константы 3 и 10.
- Низ; затраты; верх
- 300307включён1000
Обе оценки
Одно двойное неравенство работает для всего хвоста n ≥ 1.
- c; C; n₀
- 3включён10включён1включён
При $n=100$ нижняя граница равна 300, функция — 307, верхняя — 1000. Большой зазор сверху не мешает доказательству: граница должна работать, а не точно обнимать каждое значение. Во всех шагах используются одни коэффициенты 3 и 10. Последнее двойное неравенство связывает примеры общим аргументом и одновременно подтверждает обе стороны оценки для каждого $n\ge1$.
Для Θ нужны обе границы. Одна верхняя оценка, даже правдоподобно точная, ещё не доказывает порядок.