Разделяй-и-властвуй

Название

Проанализируем название - разделяй и властвуй - значит метод будет разделять задачу на две и как-то властвовать.

Мы уже разобрали метод mitm, когда мы просто решали каждую из двух частей, как исходную задачу, давайте теперь и полученные две задачи решать также : разбивая на задачи все меньше и меньше, пока не доберемся до элементарной(длины 1).

Применения

Мы уже рассматривали такой подход

• Сортировка слиянием
• Количество инверсий
• Дерево отрезков

Новые применения

• Карацуба

Дополнительно

• FFT
• Dynamic connectivity problem
• Centroid декомпозиция

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin