Алгоритмы
Разделяй и властвуй
Цели урока
- Понять парадигму Divide & Conquer
- Знать классические примеры
- Применять Master Theorem
- Решать задачи методом D&C
Предварительные знания
- Merge Sort
- Binary Search
«Разделяй и властвуй» - стратегия, которую использовали Цезарь и Наполеон. В алгоритмах она превращает O(n²) в O(n log n), а O(n³) в O(n^2.81)!
- Merge Sort, Quick Sort
- FFT (быстрое преобразование Фурье)
- Умножение больших чисел (Karatsuba)
- Умножение матриц (Strassen)
От merge sort фон Неймана к умножению Карацубы
Подход «разделяй и властвуй» старше своего названия. В 1945 году Джон фон Нейман описал merge sort, работая над EDVAC: массив делится пополам, каждая часть сортируется, затем половины сливаются. Самый яркий ранний результат появился в 1960 году. Андрей Колмогоров предполагал, что умножение двух n-значных чисел требует не меньше n в квадрате операций. 23-летний студент Анатолий Карацуба опроверг эту оценку за неделю: переписав произведение через три умножения вместо четырёх, он получил сложность около n в степени 1.585. Колмогоров был настолько впечатлён, что опубликовал результат под именем Карацубы в 1962 году. Сам термин divide and conquer закрепился позже, через учебник Ахо, Хопкрофта и Ульмана 1974 года, где его описали как общий приём проектирования алгоритмов вместе с Master Theorem для анализа рекуррентностей.
Идея: разделяй и властвуй
**Divide and Conquer (D&C)** - одна из фундаментальных парадигм в алгоритмах. Три шага:
**Когда D&C эффективен:**
- Задачу можно разбить на независимые подзадачи
- Подзадачи имеют ту же структуру, что и исходная
- Объединение результатов - эффективное
- База рекурсии - тривиальная
**D&C vs Dynamic Programming:** в D&C подзадачи независимы. В DP подзадачи перекрываются (одну считаем много раз).
Binary Search - это D&C. Какой шаг COMBINE?
Классические примеры
**1. Максимальный подмассив (Kadane D&C версия):**
**2. Быстрое возведение в степень:**
**3. Умножение Карацубы (большие числа):**
power(2, 1000) делает примерно сколько умножений?
Master Theorem
**Master Theorem** - формула для анализа D&C алгоритмов.
| Алгоритм | a | b | d | log_b(a) | T(n) |
|---|---|---|---|---|---|
| Binary Search | 1 | 2 | 0 | 0 | O(log n) |
| Merge Sort | 2 | 2 | 1 | 1 | O(n log n) |
| Karatsuba | 3 | 2 | 1 | 1.58 | O(n^1.58) |
| Strassen | 7 | 2 | 2 | 2.81 | O(n^2.81) |
**Master Theorem не универсален!** Не работает для T(n) = T(n-1) + O(n) или когда подзадачи разного размера.
T(n) = 4T(n/2) + O(n). Чему равно T(n)?
Практика: ближайшая пара точек
**Задача:** найти две ближайшие точки на плоскости. Наивно - O(n²). D&C - O(n log n)!
**Трюк «7 точек»:** в полосе шириной d для каждой точки достаточно проверить только ~7 соседей по y. Это делает COMBINE линейным!
Почему в полосе достаточно проверить O(1) соседей для каждой точки?
Divide and Conquer
- DIVIDE → CONQUER → COMBINE
- Подзадачи независимы (vs DP)
- Master Theorem: T(n) = aT(n/b) + O(n^d)
- Классика: Merge Sort, Quick Sort, Binary Search
- Продвинуто: Karatsuba, Strassen, FFT
Связанные темы
D&C - одна из главных парадигм.
- Dynamic Programming — Когда подзадачи перекрываются
- Greedy — Когда локальный оптимум = глобальный
Связанные уроки
- alg-05-merge-sort — Сортировка слиянием - канонический divide and conquer
- alg-06-quick-sort — Быстрая сортировка делит и рекурсивно обрабатывает части
- alg-21-dp — ДП переиспользует пересекающиеся подзадачи в отличие от независимых
- prog-09-recursion — Рекурсия выражает шаги разделения и объединения
- ml-29-cnn