# Lecture 7: Recurrences

Источник: https://www.youtube.com/watch?v=PvuwfciiH2U
Канал: MIT OpenCourseWare
Опубликовано: 22.07.2025

---

## Рекуррентные соотношения: от чисел Фибоначчи до сортировки слиянием 📊
[[JUMP:0:00]]

На этой лекции Зак Эйбел из MIT OpenCourseWare подводит итог изучению рекуррентных соотношений — последовательностей, заданных индуктивно. Эйбел демонстрирует, как рекурсия является фундаментальным инструментом при анализе алгоритмов, и знакомит слушателей с мощными методами поиска их закрытых форм, такими как «метод подстановки» (plug and chug) и «основная теорема» (master theorem).

### 🧩 Что такое рекуррентное соотношение?
[[JUMP:0:13]]

Рекуррентное соотношение — это, по сути, последовательность, описанная индукцией. Классическим примером являются числа Фибоначчи: $F_n = F_{n-1} + F_{n-2}$ при $n \geq 2$.

* **Проблема:** Часто алгоритмы имеют время выполнения, описываемое такими последовательностями, но работать с ними неудобно.
* **Решение:** Поиск «закрытой формы» (closed form) — формулы, позволяющей вычислить n-й член без последовательного вычисления всех предыдущих.
* **Метод:** Эйбел подчеркивает технику «догадки и проверки» (guess and check): если удалось угадать формулу, ее легко доказать индукцией.

### 🗼 Ханойская башня: экспоненциальный рост
[[JUMP:3:38]]

Задача о Ханойских башнях — классический пример рекурсивного алгоритма. По легенде, описанной Эдуаром Люка в 1883 году, в храме Ханоя монахи перемещают 64 золотых диска между тремя столбами, соблюдая два правила: перемещать по одному диску за раз и никогда не класть больший диск на меньший.

1.  **Алгоритм:** Чтобы переместить $n$ дисков, нужно:
    * Переместить $n-1$ дисков на вспомогательный столбец.
    * Переместить самый большой диск на целевой столбец.
    * Переместить $n-1$ дисков со вспомогательного столбца на целевой.
2.  **Рекуррентная формула:** $T(n) = 2T(n-1) + 1$, где $T(n)$ — количество ходов.
3.  **Закрытая форма:** $T(n) = 2^n - 1$.
4.  **Результат:** Для 64 дисков потребуется $2^{64} - 1$ ходов, что при скорости один ход в секунду составляет примерно полтриллиона лет.

### 🔀 Сортировка: от Selection Sort к Merge Sort
[[JUMP:20:43]]

Эйбел сравнивает два подхода к сортировке списков:

* **Selection Sort (Сортировка выбором):**
    * Алгоритм: находим минимальный элемент, вынимаем его, повторяем.
    * Сложность: требует $n^2/2$ сравнений (квадратичная сложность), что крайне неэффективно для больших списков.
* **Merge Sort (Сортировка слиянием):**
    * Алгоритм: разделяем список на две половины, сортируем каждую рекурсивно, затем сливаем их.
    * Слияние двух списков: берем меньший из двух первых элементов и повторяем.

### 🛠 Метод «подстановки» и Основная теорема
[[JUMP:44:23]]

Для нахождения закрытой формы времени работы Merge Sort ($M(n) = 2M(n/2) + (n-1)$) Эйбел использует два метода:

1.  **Метод «подстановки» (plug and chug):**
    * Заключается в многократной подстановке рекуррентного соотношения в самого себя.
    * Это помогает увидеть закономерность в расширении формулы и найти закрытую форму.
2.  **Основная теорема (Master Theorem):**
    * Инструмент для анализа алгоритмов типа «разделяй и властвуй» (divide and conquer).
    * Позволяет найти асимптотическую сложность ($\theta$-bound) для соотношений вида $T(n) = aT(n/b) + f(n)$.
    * Merge Sort попадает во второй случай теоремы, что дает сложность $\theta(n \log n)$.

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