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

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

Definition

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

Scope

Эта тема охватывает трехэтапную структуру алгоритмов «разделяй и властвуй» (разделение, решение, объединение), канонические примеры, такие как сортировка слиянием, быстрая сортировка, двоичный поиск и быстрое умножение целых чисел и матриц, а также анализ их времени выполнения на основе рекуррентных соотношений. Она тесно связана с основной теоремой и методами решения рекуррентных соотношений, используемыми для анализа таких алгоритмов.

Core questions

• Как проблема декомпозируется так, чтобы подпроблемы были независимыми и имели ту же форму?
• Какая работа выполняется на этапе объединения и как это влияет на общую стоимость?
• Как решаются полученные рекуррентные соотношения для получения асимптотического времени выполнения?
• Когда принцип «разделяй и властвуй» превосходит прямолинейный итеративный подход?

Key concepts

• разделяй, решай, объединяй
• рекуррентные соотношения
• основная теорема
• сортировка слиянием
• быстрая сортировка
• двоичный поиск
• умножение Карацубы
• умножение матриц Штрассена

Key theories

Основная теорема для рекуррентных соотношений

Основная теорема дает асимптотические решения в замкнутой форме для рекуррентных соотношений типа «разделяй и властвуй» вида T(n) = aT(n/b) + f(n) путем сравнения стоимости рекурсивных подпроблем со стоимостью объединения f(n).

Субквадратичное умножение через декомпозицию

Рекурсивное разбиение операндов и уменьшение количества рекурсивных умножений (как в умножении Карацубы и умножении матриц Штрассена) приводит к асимптотически более быстрым алгоритмам, чем наивные квадратичные и кубические методы.

Clinical relevance

Принцип «разделяй и властвуй» лежит в основе многих наиболее широко используемых алгоритмов: эффективная сортировка (сортировка слиянием, быстрая сортировка) в стандартных библиотеках, двоичный поиск в процедурах поиска, быстрое преобразование Фурье в обработке сигналов и изображений, а также быстрое умножение, используемое в криптографии и арифметике произвольной точности.

History

Сортировка слиянием приписывается Джону фон Нейману (1945). К. А. Р. Хоар опубликовал быструю сортировку в 1962 году. Субквадратичное умножение Карацубы 1960 года и алгоритм умножения матриц Штрассена 1969 года продемонстрировали, что рекурсивное разложение может превзойти классические границы, помогая утвердить принцип «разделяй и властвуй» как фундаментальную парадигму.

Key figures

• C. A. R. Hoare
• John von Neumann
• Anatoly Karatsuba
• Volker Strassen

Seminal works

• hoare1962
• cormen2009

Frequently asked questions

Почему сортировка слиянием имеет сложность O(n log n)?

Сортировка слиянием делит массив на две половины (log n уровней рекурсии) и на каждом уровне выполняет слияние всех элементов за линейное время, что дает рекуррентное соотношение T(n) = 2T(n/2) + O(n), которое основная теорема решает как O(n log n).

Является ли быстрая сортировка алгоритмом «разделяй и властвуй», даже если у нее нет явного шага объединения?

Да. Быстрая сортировка выполняет основную работу на этапе разделения путем разбиения вокруг опорного элемента; как только две части рекурсивно отсортированы, работа по объединению не требуется. Парадигма позволяет основной части усилий приходиться на любую из трех фаз.