Как оценить сложность рекурсивного алгоритма: рекуррентные соотношения и мастер-теорема?

Сложность рекурсии записывают рекуррентным соотношением вида `T(n) = a·T(n/b) + f(n)` и решают его мастер-теоремой, раскруткой дерева рекурсии или подстановкой.

Мастер-теорема

Для T(n) = a·T(n/b) + f(n) сравниваем f(n) с n^(log_b a) — суммарной работой в листьях:

1. f(n) растёт полиномиально медленнее — доминируют листья: Θ(n^(log_b a)).
2. Растут одинаково — работа поровну на каждом из log n уровней: Θ(n^(log_b a) · log n).
3. f(n) растёт полиномиально быстрее (и выполнено условие регулярности) — доминирует корень: Θ(f(n)).

Примеры

• Бинарный поиск: T(n) = T(n/2) + O(1) → случай 2, O(log n).
• MergeSort: T(n) = 2T(n/2) + O(n) → случай 2, O(n log n).
• Карацуба: T(n) = 3T(n/2) + O(n) → случай 1, O(n^1.585).
• Штрассен: T(n) = 7T(n/2) + O(n²) → O(n^2.81).

Когда теорема не работает

• Задача уменьшается вычитанием: T(n) = T(n−1) + O(n) раскручивается в сумму n + (n−1) + … = O(n²).
• Две ветки с вычитанием, как в наивном Фибоначчи T(n) = T(n−1) + T(n−2), дают O(φⁿ) ≈ O(1.618ⁿ).
• Разный размер подзадач — рисуем дерево рекурсии или применяем теорему Акры–Бацци.

Коротко для собеседования

Рекурсивный алгоритм описывают формулой: сколько подзадач, во сколько раз они меньше и сколько работы уходит на разбиение и сборку. Для деления на части подходит мастер-теорема, а при вычитании или неравных частях проще нарисовать дерево рекурсии и сложить работу по уровням.