DAA - разделяй и властвуй

Многие алгоритмы по своей природе являются рекурсивными для решения данной проблемы, рекурсивно решая подзадачи.

При подходе «разделяй и властвуй» проблема делится на более мелкие проблемы, затем меньшие проблемы решаются независимо, и, наконец, решения меньших проблем объединяются в решение большой проблемы.

Как правило, алгоритмы «разделяй и властвуй» состоят из трех частей:

  • Разделите проблему на несколько подзадач, которые являются небольшими экземплярами одной и той же проблемы.

  • Покорите подзадачи , решая их рекурсивно. Если они достаточно малы, решите подзадачи как базовые.

  • Объедините решения подзадач в решение исходной задачи.

Плюсы и минусы подхода «разделяй и властвуй»

Подход «разделяй и властвуй» поддерживает параллелизм, поскольку подзадачи независимы. Следовательно, алгоритм, разработанный с использованием этой методики, может работать в многопроцессорной системе или на разных машинах одновременно.

При таком подходе большинство алгоритмов разрабатываются с использованием рекурсии, поэтому управление памятью очень высоко. Для рекурсивной функции используется стек, где необходимо сохранить состояние функции.

Применение подхода «разделяй и властвуй»

Ниже приведены некоторые проблемы, которые решаются с использованием подхода «разделяй и властвуй».

  • Нахождение максимума и минимума последовательности чисел
  • Матричное умножение Штрассена
  • Сортировка слиянием
  • Бинарный поиск