DAA - разделяй и властвуй
Многие алгоритмы рекурсивны по своей природе, чтобы решить данную проблему, рекурсивно работая с подзадачами.
В divide and conquer approach, проблема делится на более мелкие проблемы, затем более мелкие проблемы решаются независимо и, наконец, решения более мелких проблем объединяются в решение большой проблемы.
Как правило, алгоритмы «разделяй и властвуй» состоят из трех частей:
Divide the problem на ряд подзадач, которые представляют собой меньшие экземпляры одной и той же проблемы.
Conquer the sub-problemsрекурсивно решая их. Если они достаточно малы, решите подзадачи как базовые случаи.
Combine the solutions к подзадачам в решение исходной проблемы.
Плюсы и минусы подхода "разделяй и властвуй"
Подход «разделяй и властвуй» поддерживает параллелизм, поскольку подзадачи независимы. Следовательно, алгоритм, разработанный с использованием этой техники, может работать в многопроцессорной системе или на разных машинах одновременно.
В этом подходе большинство алгоритмов разработано с использованием рекурсии, поэтому управление памятью очень велико. Для рекурсивной функции используется стек, в котором необходимо сохранить состояние функции.
Применение подхода «разделяй и властвуй»
Ниже приведены некоторые проблемы, которые решаются с использованием подхода «разделяй и властвуй».
- Нахождение максимума и минимума последовательности чисел
- Умножение матриц Штрассена
- Сортировка слиянием
- Бинарный поиск