Рекуррентные соотношения: от чисел Фибоначчи до сортировки слиянием 📊 0:00
На этой лекции Зак Эйбел из MIT OpenCourseWare подводит итог изучению рекуррентных соотношений — последовательностей, заданных индуктивно. Эйбел демонстрирует, как рекурсия является фундаментальным инструментом при анализе алгоритмов, и знакомит слушателей с мощными методами поиска их закрытых форм, такими как «метод подстановки» (plug and chug) и «основная теорема» (master theorem).
🧩 Что такое рекуррентное соотношение? 0:13
Рекуррентное соотношение — это, по сути, последовательность, описанная индукцией. Классическим примером являются числа Фибоначчи: $F_n = F_{n-1} + F_{n-2}$ при $n \geq 2$.
- Проблема: Часто алгоритмы имеют время выполнения, описываемое такими последовательностями, но работать с ними неудобно.
- Решение: Поиск «закрытой формы» (closed form) — формулы, позволяющей вычислить n-й член без последовательного вычисления всех предыдущих.
- Метод: Эйбел подчеркивает технику «догадки и проверки» (guess and check): если удалось угадать формулу, ее легко доказать индукцией.
🗼 Ханойская башня: экспоненциальный рост 3:38
Задача о Ханойских башнях — классический пример рекурсивного алгоритма. По легенде, описанной Эдуаром Люка в 1883 году, в храме Ханоя монахи перемещают 64 золотых диска между тремя столбами, соблюдая два правила: перемещать по одному диску за раз и никогда не класть больший диск на меньший.
- Алгоритм: Чтобы переместить $n$ дисков, нужно:
- Переместить $n-1$ дисков на вспомогательный столбец.
- Переместить самый большой диск на целевой столбец.
- Переместить $n-1$ дисков со вспомогательного столбца на целевой.
- Рекуррентная формула: $T(n) = 2T(n-1) + 1$, где $T(n)$ — количество ходов.
- Закрытая форма: $T(n) = 2^n - 1$.
- Результат: Для 64 дисков потребуется $2^{64} - 1$ ходов, что при скорости один ход в секунду составляет примерно полтриллиона лет.
🔀 Сортировка: от Selection Sort к Merge Sort 20:43
Эйбел сравнивает два подхода к сортировке списков:
- Selection Sort (Сортировка выбором):
- Алгоритм: находим минимальный элемент, вынимаем его, повторяем.
- Сложность: требует $n^2/2$ сравнений (квадратичная сложность), что крайне неэффективно для больших списков.
- Merge Sort (Сортировка слиянием):
- Алгоритм: разделяем список на две половины, сортируем каждую рекурсивно, затем сливаем их.
- Слияние двух списков: берем меньший из двух первых элементов и повторяем.
🛠 Метод «подстановки» и Основная теорема 44:23
Для нахождения закрытой формы времени работы Merge Sort ($M(n) = 2M(n/2) + (n-1)$) Эйбел использует два метода:
- Метод «подстановки» (plug and chug):
- Заключается в многократной подстановке рекуррентного соотношения в самого себя.
- Это помогает увидеть закономерность в расширении формулы и найти закрытую форму.
- Основная теорема (Master Theorem):
- Инструмент для анализа алгоритмов типа «разделяй и властвуй» (divide and conquer).
- Позволяет найти асимптотическую сложность ($\theta$-bound) для соотношений вида $T(n) = aT(n/b) + f(n)$.
- Merge Sort попадает во второй случай теоремы, что дает сложность $\theta(n \log n)$.
В завершение Эйбел отмечает: алгоритмы «разделяй и властвуй» эффективны, так как дерево рекурсии имеет логарифмическую высоту, в то время как алгоритмы вроде Ханойских башен имеют экспоненциальный рост из-за большой глубины рекурсии и ветвления.
