Рекуррентность: во что превращается рекурсия

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

Как думаешь, какой порядок у сортировки слиянием

Сортировка слиянием делит массив пополам, сортирует каждую половину тем же способом, а потом сливает две отсортированные половины за один проход - n действий. Её цена: T(n) = 2·T(n/2) + n. Порядок отсюда не виден сразу: справа опять стоит сама T, только от меньшего входа. Чтобы узнать, n·log n это или n², формулу нужно РЕШИТЬ - развернуть до тех пор, пока рекурсия не упрётся в базу.

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

Рекуррентность - это долговая расписка, которая ссылается на другие расписки поменьше: «я должен T(n), а это n наличными плюс две расписки по T(n/2)». Чтобы узнать общий долг, расписки разворачивают: каждую T(n/2) заменяют на её собственную запись, и так до самых мелких, которые гасятся наличными (база). Пока не развернёшь до дна, сумма долга неизвестна.

Механизм: из чего состоит рекуррентность

У рекуррентности две части. Рекурсивный случай: T(n) = работа на этом уровне плюс цена вызовов на меньших входах. База: T(1) = O(1) (или другой маленький вход) - место, где рекурсия останавливается и платит константу.

Форм у рекурсивного случая две, по тому, как уменьшается вход:

• вычитанием: T(n) = T(n-1) + ... - вход убывает на константу. Ханойские башни: T(n) = 2·T(n-1) + 1.
• делением: T(n) = a·T(n/b) + f(n) - вход делится в b раз, вызовов a штук, f(n) - работа на уровне. Сортировка слиянием: a = 2, b = 2, f(n) = n. Двоичный поиск: T(n) = T(n/2) + 1 - a = 1, работа константа.

База обязательна: без неё рекурсия не кончается (это разбирал раздел про рекурсию), и рекуррентность без базы не определяет T(n) ни на одном входе.

Правило

Рекуррентность = база (T(1) = O(1)) плюс рекурсивный случай (работа на уровне + вызовы на меньших входах). Решить её - найти T(n) замкнутой формулой или её порядок роста. Порядок из записи T(n) = a·T(n/b) + f(n) напрямую не читается: он зависит и от a, и от b, и от f.

Разбор: две рекуррентности, что мы уже решали

Ханойские башни: T(n) = 2·T(n-1) + 1, T(0) = 0. Разворачивая (раздел про рекурсию), получили 0, 1, 3, 7, 15 - это 2ⁿ - 1, экспонента. Вход убывал на единицу, а вызовов было два, поэтому число узлов удваивалось на каждом уровне.

Двоичный поиск: T(n) = T(n/2) + 1, T(1) = 1. Один вызов на вдвое меньшем входе плюс константа. Разворачивая: 1 + 1 + ... + 1, по одному на каждое деление пополам, а делений log₂ n - значит Θ(log n). Тот же логарифм, что мы получали мерой отрезка, только теперь из рекуррентности.

Разбор: одна форма, разная работа - разный ответ

Возьмём деление на две половины и посмотрим, как ответ зависит от работы f(n) на уровне:

• T(n) = 2·T(n/2) + 1 - работа константа. Ответ Θ(n).
• T(n) = 2·T(n/2) + n - работа линейна. Ответ Θ(n·log n).
• T(n) = 2·T(n/2) + n² - работа квадратична. Ответ Θ(n²).

Одна и та же форма 2·T(n/2), а порядки разные - n, n·log n, n². Вот почему рекуррентность решают, а не читают: ответ прячется в балансе между числом вызовов и работой f(n) на уровне. Почему выходят именно эти три порядка, посчитаем деревом уже в следующем уроке; готовую же формулу для таких случаев даст главная теорема. Пока запомни одно: работа на уровне f(n) двигает ответ, и угадать его по одной лишь форме 2·T(n/2) нельзя.

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

Две ошибки при записи. Забыть работу на уровне: у сортировки слиянием слияние стоит n, и написать T(n) = 2·T(n/2) без + n - значит потерять всю линейную работу и получить неверный Θ(n) вместо Θ(n·log n). И забыть базу: без T(1) формула ничего не задаёт - разворачивать некуда, рекурсия уходит в минус.

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

Цена любого рекурсивного алгоритма - это рекуррентность, и решить её надо до запуска: 2·T(n/2) + n доживёт до боевого объёма, 2·T(n-1) + n (то же деление работы, но вход убывает на единицу) - экспонента и не доживёт. Умение перевести код в рекуррентность и решить её - то, чем отличают быстрый рекурсивный алгоритм от медленного, не запуская ни строки.

Теперь сам

Запиши рекуррентность для этой функции (что делает obrabotat, неважно, считай её работу линейной, Θ(n)):

def f(a):
    n = len(a)
    if n <= 1:
        return
    obrabotat(a)          # Θ(n) работы
    f(a[:n//2])           # половина
    f(a[n//2:])           # вторая половина