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

Question

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

Спасибо!

Answer 1

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

Более подробную информацию см. В статье Википедии .

Answer 2

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

Answer 3

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

На самом деле самая важная вещь здесь - это сложность алгоритма, которая выражается в большой записи и nlogn для сортировки слиянием.

Для примера слияния есть другая версия, которая называется сортировка с восходящим слиянием . Это простая и нерекурсивная версия этого.

это примерно на 10% медленнее, чем рекурсивная сортировка сверху вниз в типичных системах. Вы можете обратиться к следующей ссылке для получения дополнительной информации. Это хорошо объясняется в 3-й лекции.

https://www.coursera.org/learn/introduction-to-algorithms#

Answer 4

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

Например, проблема сортировки массива размера N ничем не отличается от проблемы сортировки массива размера N / 2. За исключением того, что последний размер проблемы меньше, чем у предыдущего.

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

Answer 5

Обычно да! Сортировка слиянием является примером того же самого. Вот анимационная версия того же самого.

Answer 6

Представьте себе P - это проблема с размером n, а S - это решение. В этом случае, если P достаточно велико, чтобы его можно было разделить на подзадачи, например, P1, P2, P3, P4, ..., Pk; скажем, k подзадач, а также было бы k решений для каждой из k подзадач, таких как S1, S2, S3, ..., Sk; Теперь, если мы объединяем каждое решение подзадачи вместе, мы можем получить S-результат. В стратегии «разделяй и властвуй», что всегда является главной проблемой, все подзадачи должны быть одинаковыми. Например, если P - это сортировка, то P1, P2 и Pn тоже должны быть сортировкой. Так вот как это рекурсивно в природе. Таким образом, разделяй и властвуй будет рекурсивным.

Answer 7

Да Все Divide и Conquer всегда реализуются с использованием рекурсии.

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

1. Разделить: разбить данную проблему на подзадачи того же типа.
2. Завоевать: рекурсивно решить эти подзадачи
3. Объединить: правильно объединить ответы

Ниже приведены некоторые стандартные алгоритмы, которые являются алгоритмами «разделяй и властвуй». 1) бинарный поиск, 2) Быстрая сортировка, 3) сортировка слиянием, 4) Алгоритм Штрассена

Answer 8

Рекурсия - это метод программирования, в котором вы определяете функцию в терминах самой себя. Функция обычно вызывает себя со слегка измененными параметрами (чтобы сходиться).

1. Разделите проблему на две или более меньшие подзадачи.
2. Покорите подзадачи, решая их (рекурсивно).
3. Объедините решения подзадач в решения исходной задачи.