Θ и Ω: зажать с двух сторон

Коротко

O даёт только потолок, поэтому O(n²) честно, но нестрого и для линии. Ω(g) - зеркальное понятие: пол, f растёт не медленнее g. Θ(g) - и пол, и потолок сразу: f зажата между c₁·g и c₂·g, то есть растёт ровно как g. f = Θ(g) тогда и только тогда, когда одновременно f = O(g) и f = Ω(g). Именно Θ и называют «порядком роста» точно.

Если знаешь определения Ω и Θ и почему Θ = O и Ω одновременно - листай до «Теперь сам».

Как думаешь, чем плох потолок без пола

В прошлом уроке вышло, что n = O(n²) - истина. Но сказать про линейный алгоритм «он работает за O(n²)» - всё равно что сказать «дорога займёт не больше суток», когда едешь двадцать минут: формально верно, а по делу бесполезно. O разрешает завысить оценку сколько угодно. Чтобы оценка была честной - не завышенной, - к потолку нужен пол.

На что это похоже

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

Механизм: определения Ω и Θ

f(n) = Ω(g(n)), если существуют c > 0 и n₀, такие что

c·g(n) ≤ f(n)   для всех n ≥ n₀

Это зеркало O: там f была снизу от c·g, здесь - сверху. Ω говорит «f растёт не медленнее g».

f(n) = Θ(g(n)), если существуют c₁ > 0, c₂ > 0 и n₀, такие что

c₁·g(n) ≤ f(n) ≤ c₂·g(n)   для всех n ≥ n₀

f зажата между двумя копиями g с разными множителями - «в коридоре». Отсюда главная связь: f = Θ(g) в точности тогда, когда f = O(g) И f = Ω(g). Верхняя половина коридора - это O (потолок c₂·g), нижняя - Ω (пол c₁·g). Есть обе - есть Θ; нет хотя бы одной - Θ нет.

Правило

f = Θ(g) ⟺ f = O(g) и f = Ω(g). Чтобы доказать Θ, докажи обе границы: сверху (нашёл c₂, n₀: f ≤ c₂·g) и снизу (нашёл c₁, n₀: f ≥ c₁·g). Θ - самое сильное из трёх утверждений: из него следуют и O, и Ω, а из них по отдельности Θ не следует.

Разбор: 3n² + 500n + 2000 = Θ(n²)

Потолок уже доказан в прошлом уроке: f = O(n²) при c₂ = 4, n₀ = 505. Осталось дно. Ω(n²) требует c₁·n² ≤ 3n² + 500n + 2000. Возьмём c₁ = 3: неравенство 3n² ≤ 3n² + 500n + 2000 верно для всех n ≥ 0, ведь справа то же 3n² плюс неотрицательные слагаемые. Значит f = Ω(n²) при c₁ = 3, n₀ = 1. Обе границы есть - f = Θ(n²). Определению Θ нужен один порог n₀ на оба неравенства сразу; берут больший из двух - здесь n₀ = 505, с него держатся и дно, и потолок. Многочлен (сумма степеней n с числовыми множителями, как 3n² + 500n + 2000) всегда Θ от своего старшего члена: потолок берёт множитель побольше, дно - сам множитель старшего члена.

Коридор видно и в числах. Возьмём n = 505: старший член n² = 255 025, а сама f(505) = 3·255025 + 500·505 + 2000 = 1 019 575. Нижняя стена c₁·n² = 3·255025 = 765 075, верхняя c₂·n² = 4·255025 = 1 020 100. Значение зажато между ними: 765 075 ≤ 1 019 575 ≤ 1 020 100. И чем больше n, тем плотнее f прижимается к нижней стене 3n²: младшие слагаемые тают, множитель f стремится к трём. Верхняя стена с запасом c₂ = 4 держится про запас, на случай разгона.

Разбор: почему у алгоритма не всегда есть Θ

Сортировка вставками в ХУДШЕМ случае делает Θ(n²) действий: и не больше (O(n²) - каждый круг сдвигает не весь префикс), и не меньше (Ω(n²) - на обратно отсортированном входе сдвигает именно весь). А вот про сортировку вставками ВООБЩЕ, без указания случая, Θ назвать нельзя: на уже отсортированном входе она делает линию, на обратном - квадрат. Одной функции, зажатой с двух сторон, тут нет - есть разброс от Ω(n) (быстрее линии не бывает, весь вход надо прочесть) до O(n²). Поэтому Θ вешают на конкретный случай, а не на алгоритм целиком.

Что ломается без этого

Главная путаница - лепить Θ туда, где честно только O. «Быстрая сортировка - это Θ(n·log n)» - неверно без оговорки: в худшем случае она Θ(n²), а Θ(n·log n) - это её средний и лучший случаи. Правильно: «в среднем Θ(n·log n), в худшем O(n²)». Вторая ошибка обратная - всегда писать O из осторожности, даже когда известна и нижняя граница: тогда теряется информация, O(2ⁿ) у линейного алгоритма формально верно и совершенно бесполезно.

Зачем это в работе

Θ - это честное сравнение алгоритмов. Когда в статье пишут «наш метод Θ(n·log n), прежний был Θ(n²)», это утверждение с двух сторон: новый и не медленнее n·log n (иначе не о чем говорить), и не быстрее (обещание, которое держат). O уместно там, где известна только верхняя граница - например, для гарантии «не хуже, чем»: SLA обещает O, а не Θ, потому что клиенту важен потолок, а не то, что бывает быстрее.

Теперь сам

Докажи, что T(n) = 6n + 3 = Θ(n). Что нужно предъявить и в каком количестве?

Ответ. Нужны обе границы. Потолок (O): 6n + 3 = O(n) при c₂ = 7, n₀ = 3 (6n + 3 ≤ 7n ⟺ 3 ≤ n). Дно (Ω): 6n + 3 = Ω(n) при c₁ = 6, n₀ = 1 (6n ≤ 6n + 3 всегда). Обе границы есть, значит 6n + 3 = Θ(n). Предъявить надо две пары множителей (c₁ для дна, c₂ для потолка) и порог n₀, дальше которого держатся оба неравенства.

Главное

Ω(g) - пол: f ≥ c·g с какого-то n₀, «не медленнее g». Θ(g) - коридор: c₁·g ≤ f ≤ c₂·g, «ровно как g». f = Θ(g) ⟺ f = O(g) и f = Ω(g), поэтому Θ доказывают двумя границами. O - когда известен только потолок; Θ - когда известны обе стены. У алгоритма Θ есть лишь для фиксированного случая: если лучший и худший случаи разного порядка, единой Θ нет.