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