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

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

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

Я запутался .


recursion divide-and-conquer
person Gary Gauh    schedule 03.02.2012    source источник
comment
вы задали два разных вопроса, пожалуйста, поясните   -  person Marcelo Diniz    schedule 03.02.2012

Ответы (1)


arrow_upward
4
arrow_downward

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

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

Практическое применение алгоритма Divide and Conquer состоит из трех шагов:

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

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

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

//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);
person RaviSharma    schedule 03.02.2012