Источник: Nuances of Programming
Предыдущая часть: “Структуры данных: асимптотический анализ”
При подходе «разделяй и властвуй» задача делится на мелкие подзадачи, каждая из которых решается независимо. При их делении на еще более мелкие подзадачи в конце концов настает момент, когда дальнейшее деление невозможно. Эти мельчайшие «атомарные» подзадачи и решаются. Решения всех подзадач в итоге объединяются, и получается решение исходной задачи:
В целом подход «разделяй и властвуй» рассматривается как трехэтапный процесс.
Разделение/разбиение
На этом этапе исходная задача разбивается на более мелкие подзадачи, каждая из которых является ее частью. Причём обычно применяется рекурсивный подход и подзадачи делятся до тех пор, пока не будут все неделимыми. Здесь подзадачи, оставаясь частью самой задачи, становятся по сути атомарными.
Завоевание/решение
На этом этапе и решается много мелких подзадач. Причём считается, что они решаются независимо.
Слияние/комбинирование
Решения мелких подзадач комбинируются, и получается решение исходной задачи. В этом алгоритмическом подходе работа осуществляется рекурсивно, а этапы завоевания и слияния выполняются настолько близко, что кажутся единым целым.
Примеры
На подходе «разделяй и властвуй» основаны следующие алгоритмы:
- сортировка слиянием;
- быстрая сортировка;
- двоичный поиск;
- умножение матриц Штрассена;
- поиск ближайшей пары (точек).
Многие задачи программирования решаются различными способами, и приведенные выше алгоритмы — хороший пример использования подхода «разделяй и властвуй».
Читайте также: