Главная теорема: готовая формула для деления

Коротко

Главная теорема даёт ответ для рекуррентностей вида T(n) = a·T(n/b) + f(n) без дерева и подстановки. Сравниваешь работу одного вызова вне рекурсии f(n) с числом листьев n^(log_b a). Полиномиально меньше - Θ(n^(log_b a)) (решают листья); того же порядка - Θ(n^(log_b a)·log n); полиномиально больше и выполнена регулярность - Θ(f(n)) (решает корень). Три случая - это ровно «листья, число уровней, корень» из прошлой главы, только записанные формулой.

Если знаешь три случая главной теоремы и что n^(log_b a) - это число листьев дерева, листай до «Теперь сам».

Как думаешь, зачем формула, если есть дерево

Дерево помогает разбирать рекуррентности, но каждый раз заново: нарисуй, посчитай цену уровня, сложи. Для самого частого вида - a вызовов на входе в b раз меньше плюс работа f(n) вне рекурсии в одном вызове - это делали столько раз, что ответ свернули в теорему. Подставил три числа (a, b, f) - получил порядок. Дерево при этом никуда не делось: теорема - его свёрнутый результат, и понимать её надо через дерево.

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

Это как таблица умножения против сложения столбиком. Сложить 7+7+7+7 можно всегда, но 7·4 быстрее, если таблицу знаешь. Главная теорема - «таблица» для рекуррентностей деления: три заученных случая вместо разворачивания дерева каждый раз. Но как таблица умножения стоит на сложении, так и теорема стоит на дереве - без него это три формулы, которые не понять и легко перепутать.

Механизм: откуда берётся n^(log_b a)

Главное число теоремы - n^(log_b a). Это не магия, это ЧИСЛО ЛИСТЬЕВ дерева рекурсии, и вот почему.

Вход делится на b каждый уровень (глубина log_b n), а вызовов на каждом в a раз больше - листьев a^(log_b n), и это то же самое, что n^(log_b a).

Вход делится на b каждый уровень, поэтому до размера 1 спускаемся за log_b n уровней - это глубина дерева. На каждом уровне вызовов в a раз больше, чем на предыдущем: на уровне k их a^k. Значит листьев (самый нижний уровень, k = log_b n) ровно a^(log_b n).

Теперь тождество: a^(log_b n) = n^(log_b a). Проверяется логарифмом - возьмём log_b от обеих частей. Слева log_b(a^(log_b n)) = log_b n · log_b a. Справа log_b(n^(log_b a)) = log_b a · log_b n. Это одно и то же произведение - значит равны логарифмы, а раз логарифм разным числам даёт разное (функция строго растёт), то равны и сами числа. Вот почему в теореме стоит именно n^(log_b a), а не, скажем, n·a или a^b: это записанное через n число листьев дерева.

Работа f(n) относится к одному узлу размера n, а не ко всему уровню. На уровне k узлов a^k, каждый размера n/b^k, поэтому суммарная нерекурсивная работа уровня равна a^k·f(n/b^k). Например, для 4·T(n/2)+n первые уровни стоят n, 2n, 4n. Число листьев выше подсчитано для степеней b; округления размеров сохраняют порядок роста.

Правило

Главная теорема для T(n) = a·T(n/b) + f(n) (a ≥ 1, b > 1): сравни работу одного вызова вне рекурсии f(n) с числом листьев n^(log_b a). Базовый случай стоит Θ(1), f(n) неотрицательна.

f(n) полиномиально МЕНЬШЕ n^(log_b a) (отстаёт на множитель n^ε при каком-то ε > 0) → T(n) = Θ(n^(log_b a)) (случай 1, решают листья).
f(n) того же порядка, Θ(n^(log_b a)) → T(n) = Θ(n^(log_b a)·log n) (случай 2, решает число уровней).
f(n) полиномиально БОЛЬШЕ n^(log_b a) и при достаточно больших n выполнена регулярность a·f(n/b) ≤ c·f(n) для некоторой константы c < 1 → T(n) = Θ(f(n)) (случай 3, решает корень).

Разбор: сортировка слиянием через теорему

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

Разбор: двоичный поиск через теорему

T(n) = T(n/2) + 1. Здесь a = 1, b = 2, f(n) = 1. Число листьев: n^(log_2 1) = n^0 = 1 - один лист, ведь вызов всего один, дерево не ветвится. Сравниваем f(n) = 1 с n^(log_b a) = 1 - одного порядка, случай 2. Ответ Θ(1·log n) = Θ(log n). Логарифм здесь - от числа уровней, а n^(log_b a) = 1 показывает, что листья ничего не решают: их всего один.

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

Три ошибки. Спутать, что с чем сравнивают: сравнивают f(n) с n^(log_b a), а не a с b и не f с n. Забыть, что «меньше» и «больше» должны быть ПОЛИНОМИАЛЬНЫМИ (на множитель n^ε), - иначе попадёшь в зазор, где теорема молчит (следующий урок). И применить теорему к чужой форме: если вход убывает вычитанием (T(n-1)) или делится неровно, a·T(n/b) не про это - теорема не для них.

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

Многие алгоритмы «разделяй и властвуй» - сортировка слиянием, умножение Карацубы, быстрое преобразование Фурье - дают a·T(n/b) + f(n). Их порядок читается главной теоремой за секунды, без дерева: увидел T(n) = 8·T(n/2) + n², посчитал n^(log_2 8) = n³ против n², листья больше - ответ Θ(n³). На код-ревью или собеседовании это разница между «мгновенно назвал» и «рисую дерево пять минут».

Теперь сам

Реши главной теоремой: T(n) = 4·T(n/2) + n (a = 4, b = 2, f(n) = n).

Ответ. Число листьев: n^(log_2 4) = n^2. Сравниваем f(n) = n с n^(log_b a) = n². Работа корня n полиномиально МЕНЬШЕ n² (меньше на множитель n, то есть на n^ε с ε = 1) - случай 1, решают листья. Ответ Θ(n²). Проверка смыслом: вызовов четыре, а вход делится лишь пополам, поэтому дерево широкое - листьев n², и они перевешивают линейную работу наверху.

Главное

Главная теорема сравнивает f(n), работу одного вызова вне рекурсии, с n^p, где p = log_b a: это порядок числа листьев. Если f(n) = O(n^(p−ε)) при постоянном ε > 0, ответ Θ(n^p); если f(n) = Θ(n^p), ответ Θ(n^p·log n); если f(n) = Ω(n^(p+ε)) и выполнена регулярность a·f(n/b) ≤ c·f(n) при постоянном c < 1, ответ Θ(f(n)). На уровне k работа равна a^k·f(n/b^k), а не f(n).