Как пользоваться основной теоремой о рекуррентных соотношениях (мастер-теоремой) для оценки сложности?
Готовлюсь к собесу по алгоритмам. Постоянно встречаю рекурренты вида T(n) = a·T(n/b) + f(n) и для разделяй-и-властвуй надо быстро называть сложность. Слышал, что есть «основная теорема о рекуррентных соотношениях» (master theorem), но формулировка с тремя случаями меня пугает. Можете объяснить по-человечески и показать на сортировке слиянием и бинпоиске?
3 ответа
Мастер-теорема — это быстрый способ решить рекурренты вида T(n) = a·T(n/b) + f(n), где:
a— на сколько подзадач разбиваем (≥ 1),b— во сколько раз меньше каждая подзадача (> 1),f(n)— работа вне рекурсии (разбить + собрать).
Вся идея: сравниваем f(n) с «весом рекурсии» — функцией n^(log_b a). Кто перевесит, тот и определяет ответ. Три случая:
- Рекурсия тяжелее. Если
f(n)растёт МЕДЛЕННЕЕ, чемn^(log_b a)→T(n) = Θ(n^(log_b a)). - Поровну. Если
f(n) = Θ(n^(log_b a))→ добавляется логарифмический множитель:T(n) = Θ(n^(log_b a) · log n). - Верхний уровень тяжелее. Если
f(n)растёт БЫСТРЕЕn^(log_b a)(и выполнено условие регулярности) →T(n) = Θ(f(n)).
Теперь примеры.
Сортировка слиянием: делим массив на 2 половины (a = 2), каждая вдвое меньше (b = 2), слияние линейно (f(n) = n).
log_b a = log_2 2 = 1, значит порог —n^1 = n.f(n) = n = Θ(n)— это РОВНО порог → случай 2.- Ответ:
T(n) = Θ(n log n). Знакомо, да?
Бинарный поиск: одна подзадача (a = 1), вдвое меньше (b = 2), работа на уровне — константа (f(n) = 1).
log_b a = log_2 1 = 0, порог —n^0 = 1.f(n) = 1 = Θ(1)— ровно порог → случай 2.- Ответ:
T(n) = Θ(1 · log n) = Θ(log n). Тоже сходится.
Бонус — обход бинарного дерева T(n) = 2T(n/2) + 1: log_2 2 = 1, порог n, а f(n) = 1 РАСТЁТ медленнее n → случай 1 → T(n) = Θ(n).
Лайфхак для собеса: посчитай log_b a, мысленно нарисуй n^(log_b a) и сравни с f(n). Дальше просто три исхода: меньше — случай 1, равно — случай 2 (плюс log), больше — случай 3.
Важная оговорка: мастер-теорема покрывает не всё. Она НЕ применима, когда a или b не константы, когда f(n) не полиномиально-сравнима с порогом (между случаями есть «дыры», например f(n) = n log n против n — это не чистый случай 3), или когда подзадачи разного размера, как в быстрой сортировке в худшем случае T(n) = T(n-1) + n. Для таких — метод подстановки или дерево рекурсии.
Запоминалка для разделяй-и-властвуй: если на каждом уровне суммарная работа примерно одинаковая (как merge sort) — будет лишний log n (случай 2). Если работа быстро тает вниз по дереву (вся нагрузка наверху) — доминирует корень, Θ(f(n)) (случай 3). Если, наоборот, разрастается к листьям — доминируют листья, Θ(n^(log_b a)) (случай 1). Часто можно угадать случай ещё до формул, просто прикинув, где «тяжелее».
