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