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

Question

Когда мы говорим о разделяй и властвуй, мы всегда используем рекурсию. Я уже знал, что разделяй и властвуй - это метод проектирования алгоритма, но у меня есть один вопрос:

Являются ли все алгоритмы «разделяй и властвуй» рекурсией или, другими словами, мысль «разделяй и властвуй» используется во всех рекурсиях?

Я не совсем понимаю .

Answer 1

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

По определению

Существует три этапа применения алгоритма «разделяй и властвуй» на практике:

• Разделите проблему на одну или несколько подзадач.
• Завоевать подзадачи, решая их рекурсивно . Если подзадача размеры достаточно малы, однако, просто решить подзадачи в прямолинейно.
• Объедините решения подзадач в решение для исходная задача.

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

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

//binary search for x, in array A[1 .. N]

min := 1;
max := N;
repeat
  mid := (min+max) div 2;
  if x > A[mid] then
    min := mid + 1;
  else
    max := mid - 1;
until (A[mid] = x) or (min > max);