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

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

Skillfactory.ru

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

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

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

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

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

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

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

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

Примеры

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

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

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

Skillfactory.ru

Читайте также:

Читайте нас в TelegramVK и Яндекс.Дзен

Предыдущая статьяРазвертывание Cloud Functions в GCP с помощью Terraform
Следующая статьяСтруктуры данных: динамическое программирование