Конспект раздела: рекуррентности и амортизация

Карта раздела

Раздел отвечает на вопрос «сколько стоит алгоритм, который вызывает сам себя или делает редкие дорогие операции». Три главы - три инструмента.

методы решения    ->  рекуррентность деревом (сумма по уровням) и подстановкой
     |
главная теорема   ->  готовая формула для a·T(n/b)+f(n): три случая
     |
амортизация       ->  средняя цена по серии: агрегат, предоплата, потенциал

Дерево решений: какая рекуррентность каким методом

Что перед тобой	Инструмент	Ответ
`a·T(n/b) + f(n)`, стандартная	главная теорема	сравни `f` с `n^(log_b a)`
та же, но `f` в зазоре (разрыв на `log`)	дерево рекурсии	напр. `2T(n/2)+n·log n → n·log²n`
нестандартная (`T(n-1)`, `T(n/3)+T(2n/3)`, `T(√n)`)	дерево + подстановка	сумма по уровням, потом доказать
догадка есть, нужна строгость	подстановка	предположи для `n/2`, замкни константой
серия операций, редкие дорогие	амортизация	`T(серии)/n`; предоплата; потенциал

Три случая главной теоремы

Для T(n) = a·T(n/b) + f(n), водораздел n^(log_b a) (число листьев):

Случай	Условие	Ответ	Кто решает
1	`f` полиномиально меньше `n^(log_b a)`	`Θ(n^(log_b a))`	листья
2	`f = Θ(n^(log_b a))`	`Θ(n^(log_b a)·log n)`	число уровней
3	`f` полиномиально больше (+ регулярность)	`Θ(f(n))`	корень

Зазор - если разрыв между f и водоразделом лишь на множитель-логарифм, а не на n^ε: теорема молчит, решают деревом.

Три метода амортизации

Метод	Как	Условие
агрегатный	общую цену серии делят на `n`	считать всю серию
предоплата	назначить `ĉ`, копить кредит	кредит `≥ 0` всегда
потенциал	`ĉ = c + Φ(после) − Φ(до)`	`Φ ≥ 0`, `Φ(D₀) = 0`

Итог главы: вставка в динамический массив - O(1) амортизированно (Φ = 2·num − size), но только при удвоении буфера, а не росте на константу.

Сквозная нить - геометрический ряд

Он связывает весь раздел. Число уровней дерева при делении - log n (деление пополам до единицы). Число листьев n^(log_b a). Суммарное копирование при удвоениях массива - 1 + 2 + 4 + ... + n < 2n. Всюду одно: деление и удвоение дают геометрию, а она линейна и логарифмична, тогда как вычитание и рост на константу дают арифметику - квадрат и экспоненту.

Связи с остальным курсом

Сортировки - главный потребитель: слияние (2T(n/2)+n → n·log n), быстрая сортировка (та же рекуррентность в среднем), их нижняя граница.

Массивы и списки держатся на амортизации: динамический массив, стек, очередь - их O(1)-операции доказаны здесь.

Умножение и геометрия дают случаи 1 и 3: Штрассен (7T(n/2)+n² → n^2.81), Карацуба (3T(n/2)+n → n^1.585).

Неравные подзадачи

Задача	Инструмент	Условие или граница
Подзадачи разных долей	Акра-Бацци	Найди p из суммы aᵢbᵢ^p=1; проверь регулярность f и базовые значения.
Дробный показатель	Θ(n^p)	Округление p внутри Θ меняет асимптотический класс.

Чек-лист: объясни своими словами

Что такое рекуррентность и почему у неё обязательна база.
Чем форма T(n-1) отличается от a·T(n/b)+f(n) по числу уровней.
Почему 2T(n/2)+n даёт n·log n, и как это видно из дерева.
Как подстановка доказывает оценку и по какому признаку отвергает неверную.
Что такое n^(log_b a) и почему это число листьев.
Три случая главной теоремы и кто в каждом решает: листья, уровни, корень.
Зачем нужно условие регулярности и что такое зазор между случаями.
Чем амортизированная цена отличается от среднего случая.
Три метода амортизации и что гарантирует каждый.
Почему вставка в динамический массив O(1) амортизированно и при чём удвоение.

Что дальше

Рекуррентности решаются, амортизация посчитана - весь аппарат стоимости для рекурсивных и «редко дорогих» алгоритмов готов. Дальше - массивы, списки и абстрактные типы данных: где амортизация из этого раздела заработает на очереди и стеке, а рекуррентности - на первом большом классе, сортировках.