Конспект: рекуррентности

Понятия

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

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

Решить рекуррентность - найти T(n) в замкнутом виде или её порядок. Из записи a·T(n/b)+f(n) порядок напрямую не читается.

Дерево рекурсии - разложение рекуррентности в сумму по уровням: узел - работа вызова без вложенных, цена уровня - сумма его узлов, ответ - сумма по уровням.

Метод подстановки - доказательство оценки индукцией по размеру входа: угадать форму, предположить её для меньших входов, подставить и подобрать константу.

Что унести

Порядок прячется в балансе числа вызовов и работы на уровне. Одна форма 2·T(n/2) при разной f даёт разные ответы: +1 → Θ(n), +n → Θ(n·log n), +n² → Θ(n²). Поэтому рекуррентность решают, а не читают.

Дерево складывает по уровням. Для T(n)=2·T(n/2)+n каждый уровень стоит n (вызовов 2ⁱ, работы у каждого n/2ⁱ, вместе n), уровней log₂ n, итог Θ(n·log n). Число уровней задаёт закон убывания входа: деление - log n, вычитание - n. Отсюда пропасть: 2·T(n/2)+n это n·log n, а 2·T(n-1)+1 - экспонента 2ⁿ−1 (Ханой).

Когда цена уровня не постоянна, решает больший конец: убывает вниз - корень (+n² → Θ(n²)), растёт вниз - листья (+1 → Θ(n)), постоянна - число уровней (+n → Θ(n·log n)). Это и есть три случая главной теоремы из следующей главы.

Подстановка доказывает то, что дерево угадало. Угадываешь T(n) ≤ c·n·log₂ n, предполагаешь для n/2, подставляешь в рекуррентность и подбираешь c, чтобы неравенство для n замкнулось. База берётся не на единице (там log₂1=0 обнуляет оценку), а на входе побольше. Лишнее слагаемое, которое не уходит, - признак неверной догадки: так O(n) честно отвергается для 2·T(n/2)+n.

Дерево и подстановка работают в паре: прикинул порядок деревом за минуту, доказал подстановкой, когда цена ошибки высока.

Ловушки джокера

Прочитал порядок из записи. 2·T(n/2)+f без решения ничего не говорит: при f=1 это n, при f=n² - n². Одна форма - разные порядки.

Забыл работу на уровне или базу. T(n)=2·T(n/2) без +n теряет линейное слияние и даёт неверный Θ(n). Без базы формула не определяет T(n) ни на одном входе.

Спутал число уровней. У деления это log n, у вычитания - n. Перепутал - и n·log n превратилось в экспоненту или наоборот.

Забыл листья. У 2·T(n/2)+1 вся цена в листьях; посчитав только внутренние уровни, получишь Θ(log n) вместо верного Θ(n).

В подстановке отбросил лишнее слагаемое. Доказывать надо ровно угаданную форму до последнего слагаемого; уходящее +n - сигнал, что догадка мала, а не мусор.

Начал индукцию с n=1. Там оценка c·n·log n обнуляется и не накрывает T(1)>0. Базу берут на входе побольше.

Проверь себя

Что такое рекуррентность и почему у неё обязательна база?

Чем форма T(n-1) отличается от a·T(n/b)+f(n) и как это влияет на число уровней дерева?

Почему у 2·T(n/2)+n каждый уровень стоит n, а всего выходит n·log n?

Когда ответ определяет корень, когда листья, а когда число уровней?

Как подстановка доказывает оценку и по какому признаку она отвергает неверную догадку?

Почему базу индукции берут не при n=1?