Структуры данных - разделяй и властвуй
В подходе «разделяй и властвуй» рассматриваемая проблема делится на более мелкие подзадачи, а затем каждая проблема решается независимо. Когда мы продолжаем разделять подзадачи на еще более мелкие подзадачи, мы в конечном итоге можем достичь стадии, когда разделение станет невозможным. Эти «атомарные» наименьшие возможные подзадачи (дроби) решены. Окончательно решение всех подзадач объединяется, чтобы получить решение исходной проблемы.
В широком смысле мы можем понять divide-and-conquer подход в трехэтапном процессе.
Разделить / Разбить
Этот шаг включает разбиение проблемы на более мелкие подзадачи. Подзадачи должны представлять собой часть исходной проблемы. На этом этапе обычно используется рекурсивный подход для разделения проблемы до тех пор, пока ни одна из подзадач не станет делимой. На этом этапе подзадачи становятся атомарными по своей природе, но все же представляют некоторую часть реальной проблемы.
Завоевать / Решить
На этом этапе необходимо решить множество более мелких подзадач. Обычно на этом уровне проблемы считаются «решенными» сами по себе.
Слияние / объединение
Когда более мелкие подзадачи решены, этот этап рекурсивно объединяет их, пока они не сформулируют решение исходной проблемы. Этот алгоритмический подход работает рекурсивно, и этапы "завоевать и объединить" работают так близко, что кажутся единым целым.
Примеры
Следующие компьютерные алгоритмы основаны на divide-and-conquer подход к программированию -
- Сортировка слиянием
- Быстрая сортировка
- Бинарный поиск
- Умножение матриц Штрассена
- Ближайшая пара (баллы)
Существуют различные способы решения любой компьютерной проблемы, но упомянутые выше являются хорошим примером подхода «разделяй и властвуй».