Применяем теорему и условие регулярности

Если умеешь применить теорему во всех трёх случаях и знаешь, зачем нужно условие регулярности, листай до «Теперь сам».

Как думаешь, всегда ли «корень больше» значит Θ(f(n))

В случае 3 работа f(n) наверху больше числа листьев, и хочется сказать: раз корень дороже всех, ответ Θ(f(n)). Почти так - но с оговоркой. «Корень дороже листьев» сравнивает только два края дерева. А вдруг работа по уровням убывает вниз так медленно, что средние уровни в сумме перевесят корень? Чтобы этого не случилось, теорема требует отдельную проверку - условие регулярности.

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

Это как проверить, что долг гасится всерьёз, а не только «первый платёж крупный». Если каждый следующий слой работы составляет какую-то постоянную долю c < 1 от предыдущего (пусть даже 0.9), сумма всех слоёв - геометрический ряд, и его определяет первый слой, корень. А если слои убывают еле-еле, их набирается много, и «крупный первый платёж» тонет в хвосте. Условие регулярности - это и есть «каждый слой заметно меньше предыдущего».

Механизм: три шага и проверка регулярности

Порядок один и тот же.

1. Выпиши a, b, f(n). Посчитай водораздел n^(log_b a).
2. Сравни f(n) с n^(log_b a) - кто полиномиально больше (на множитель n^ε).
3. Назови случай и выпиши ответ.

Для случая 3 добавь шаг 4: проверь a·f(n/b) ≤ c·f(n) при каком-нибудь постоянном c < 1. Смысл: a·f(n/b) - это суммарная работа СЛЕДУЮЩЕГО уровня вниз (там a вызовов размера n/b). Условие говорит, что уровень ниже стоит не больше доли c от текущего. Значит по уровням работа падает геометрически, весь ряд сходится к первому слагаемому, и ответ Θ(f(n)) - работа корня.

Правило

Схема применения: n^(log_b a) → сравнить с f(n) → случай. В случае 3 дополнительно проверить регулярность a·f(n/b) ≤ c·f(n), c < 1. Для f(n) = nᵏ условие выполняется всегда, когда случай 3 вообще подходит по степеням, - его проверяют формально, а спотыкаются на нём только специально подобранные f.

Разбор: случай 1, листья перевешивают

T(n) = 8·T(n/2) + n². Здесь a = 8, b = 2, f(n) = n². Водораздел: n^(log_2 8) = n³. Сравниваем f(n) = n² с n³: работа одного вызова вне рекурсии полиномиально МЕНЬШЕ числа листьев (на множитель n, то есть ε = 1). Случай 1, решают листья, ответ Θ(n³). Смыслом: восемь вызовов при делении лишь пополам - дерево очень широкое, листьев n³, и квадратичная работа наверху рядом с ними ничтожна.

Разбор: случай 3, корень перевешивает, и регулярность

T(n) = 3·T(n/4) + n. Здесь a = 3, b = 4, f(n) = n. Водораздел: n^p, где p = log_4 3 ≈ 0,79248. Сравниваем f(n) = n с n^p: работа корня полиномиально БОЛЬШЕ, отношение равно n^(1−p), где 1−p > 0. Похоже на случай 3 - проверим регулярность: a·f(n/b) = 3·(n/4) = 0.75·n, а c·f(n) = c·n. Неравенство 0.75·n ≤ c·n держится при c = 0.75 < 1. Условие выполнено, случай 3 подтверждён, ответ Θ(f(n)) = Θ(n). Три вызова на входе вчетверо меньше - дерево узкое, работы вниз всё меньше, и линейная работа корня всё и решает.

Разбор: случай 2, всё уравновешено

T(n) = 2·T(n/2) + n (сортировка слиянием). a = 2, b = 2, f(n) = n. Водораздел n^(log_2 2) = n. Работа корня n того же порядка, что число листьев n, - случай 2. Ответ Θ(n^(log_b a)·log n) = Θ(n·log n). Здесь ни листья, ни корень не перевешивают, поэтому к n добавляется множитель log n от числа уровней - в точности то, что дерево показывало в прошлой главе.

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

Две ошибки. Объявить случай 3, не проверив регулярность, - обычно ответ верный, но на подстроенных f (например f(n) = n²·sin²n + n) регулярность рвётся, и Θ(f(n)) неверно. И перепутать направление: a·f(n/b) - это уровень ВНИЗ (вход меньше в b раз), а не вверх; подставлять надо n/b, а не n·b.

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

Случай 3 с регулярностью - это про алгоритмы, где основная работа наверху, на неделёном входе: T(n) = 2·T(n/2) + n² (ответ Θ(n²)) - вся цена в квадратичной склейке, рекурсия дёшева. Знать, что решает корень, важно для оптимизации: ускорять надо f(n), а не рекурсивную часть - на неё время всё равно почти не уходит. Это прямое указание, какую строчку кода профилировать.

Теперь сам

Реши теоремой: T(n) = 2·T(n/2) + n³. Определи случай, ответ и, если нужно, проверь регулярность.