Многие алгоритмы по своей природе являются рекурсивными для решения данной проблемы, рекурсивно решая подзадачи.
При подходе «разделяй и властвуй» проблема делится на более мелкие проблемы, затем меньшие проблемы решаются независимо, и, наконец, решения небольших проблем объединяются в решение большой проблемы.
Как правило, алгоритмы «разделяй и властвуй» состоят из трех частей:
-
Разделите проблему на несколько подзадач, которые являются небольшими экземплярами одной и той же проблемы.
-
Покорите подзадачи , решая их рекурсивно. Если они достаточно малы, решите подзадачи как базовые.
-
Объедините решения подзадач в решение исходной задачи.
Разделите проблему на несколько подзадач, которые являются небольшими экземплярами одной и той же проблемы.
Покорите подзадачи , решая их рекурсивно. Если они достаточно малы, решите подзадачи как базовые.
Объедините решения подзадач в решение исходной задачи.
Плюсы и минусы подхода «разделяй и властвуй»
Подход «разделяй и властвуй» поддерживает параллелизм, поскольку подзадачи независимы. Следовательно, алгоритм, который разработан с использованием этого метода, может работать в многопроцессорной системе или на разных машинах одновременно.
При таком подходе большинство алгоритмов разрабатываются с использованием рекурсии, поэтому управление памятью очень высоко. Для рекурсивной функции используется стек, где необходимо сохранить состояние функции.
Применение подхода «разделяй и властвуй»
Ниже приведены некоторые проблемы, которые решаются с использованием подхода «разделяй и властвуй».