Что такое принцип «разделяй и властвуй» и какие алгоритмы на нём построены?

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

Три шага

1. Divide — разбить вход (пополам, вокруг опорного элемента, по координате).
2. Conquer — рекурсивно решить части; маленькие — напрямую.
3. Combine — собрать ответ; именно здесь обычно сосредоточена основная работа.

Примеры

• MergeSort — O(n log n); попутно при слиянии считается число инверсий.
• QuickSort — вся работа в divide (partition), combine пустой.
• Карацуба — умножение чисел за O(n^1.585) вместо O(n²).
• Ближайшая пара точек на плоскости — O(n log n) вместо O(n²).
• БПФ — умножение многочленов за O(n log n).
• Быстрое возведение в степень: xⁿ = (x^(n/2))² (плюс x для нечётного n) — O(log n) умножений вместо n.

Отличие от ДП и плюсы

• Подзадачи не пересекаются. Если пересекаются (как в Фибоначчи), наивная рекурсия пересчитывает одно и то же экспоненциально — нужно ДП.
• Независимые части естественно распараллеливаются: fork-join, ForkJoinPool в Java, параллельный merge sort.

Коротко для собеседования

Разделяй и властвуй сводит задачу к нескольким независимым меньшим и склеивает их ответы — так устроены MergeSort, QuickSort, Карацуба и БПФ. Если подзадачи пересекаются, нужна ДП, а на маленьких входах рекурсия проигрывает простому алгоритму — отсюда гибриды с сортировкой вставками.