Разделяй и властвуй решает задачу путем (1) разделения её на меньшие подзадачи, (2) решения каждой рекурсивно и (3) объединения результатов. Многие эффективные алгоритмы следуют этому шаблону.
Если подзадачи независимы и быстро сокращаются, общий объём работы подчиняется рекуррентному соотношению, которое можно анализировать с помощью Основной теоремы.
def max_dc(arr, lo, hi):
if lo == hi: # base case: one element
return arr[lo]
mid = (lo + hi) // 2
left = max_dc(arr, lo, mid) # conquer left
right = max_dc(arr, mid + 1, hi) # conquer right
return max(left, right) # combine
max_dc([3, 9, 2, 7], 0, 3) # -> 9
Обычно T(n) = a·T(n/b) + f(n); для merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Используйте, когда задача чётко делится на независимые подзадачи. Если подзадачи пересекаются, предпочтите динамическое программирование (чтобы избежать пересчета). Накладные расходы рекурсии и шаг объединения могут доминировать для малых входных данных.
Разделяй и властвуй — это переиспользуемый шаблон, лежащий в основе большой доли эффективных алгоритмов.
Распознавание паттерна позволяет быстро выводить и анализировать новые алгоритмы с помощью рекуррентных соотношений.
Он также естественным образом отображается на параллелизм, так как независимые подзадачи могут выполняться одновременно.