Структуры данных: подход «разделяй и властвуй»

Предыдущая часть: “Структуры данных: асимптотический анализ”

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

В целом подход «разделяй и властвуй» рассматривается как трехэтапный процесс.

Разделение/разбиение

На этом этапе исходная задача разбивается на более мелкие подзадачи, каждая из которых является ее частью. Причём обычно применяется рекурсивный подход и подзадачи делятся до тех пор, пока не будут все неделимыми. Здесь подзадачи, оставаясь частью самой задачи, становятся по сути атомарными.

Завоевание/решение

На этом этапе и решается много мелких подзадач. Причём считается, что они решаются независимо.

Слияние/комбинирование

Решения мелких подзадач комбинируются, и получается решение исходной задачи. В этом алгоритмическом подходе работа осуществляется рекурсивно, а этапы завоевания и слияния выполняются настолько близко, что кажутся единым целым.

Примеры

На подходе «разделяй и властвуй» основаны следующие алгоритмы:

• сортировка слиянием;
• быстрая сортировка;
• двоичный поиск;
• умножение матриц Штрассена;
• поиск ближайшей пары (точек).

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