Разделяй и властвуй

Разделяй и властвуй

Метод «разделяй и властвуй» — это метод, который иногда позволяет находить эффективные решения алгоритмических задач. Идея состоит в том, чтобы вырезать первоначальную проблему, размер нет, на несколько подзадач меньшего размера, а затем рекомбинировать частичные решения до получения окончательного решения.

Принцип

Разделяй и властвуй

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

Алгоритм «разделяй и властвуй» разбит на три шага:

  1. Разделить: проблема разделена на подзадачи размера ч/б. Эти подпроблемы имеют ту же природу, что и их родитель. Поэтому мы находимся в присутствии в одинаковые подзадачи. Когда б=2, мы говорим о дихотомии.
  2. Правило: подзадачи решаются рекурсивно.
  3. Рекомбинация: решения подзадач рекомбинируются для восстановления решения исходной задачи.

Пример

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

Наивным способом было бы зациклить, где a*= x с a = 1 изначально. сложность поэтому наивный метод является линейным 0(n).

Чтобы использовать метод «разделяй и властвуй», нам нужно найти математическую программу, которая перепишет нашу проблему в эквивалентные подзадачи. Поскольку это рекурсивный метод, не забудьте указать конечное состояние. Таким образом, мы имеем следующую математическую программу:

разделяй и властвуй быстрое возведение в степень

Алгоритм следующий:

двойная мощность (двойной x, int n) {
   если (n==0) вернуть 1;
   еще {
      если (n%2==0) мощность возврата (x*x, n/2);
      еще вернуть x*power(x*x, (n-1)/2);
      конец, если
   конец, если
}

Его сложность составляет 0(log n) — размер полного бинарного дерева при нет пики.

Делиться
ru_RURU
%d такие блоггеры, как: