Имеют ли итеративные и рекурсивные версии алгоритма одинаковую сложность по времени?

Question

Скажем, например, итеративные и рекурсивные версии ряда Фибоначчи. Они имеют одинаковую сложность времени?

Answer 1

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

int iterative_fib(int n) {
   if (n <= 2) {
     return 1;
   }
   int a = 1, b = 1, c;
   for (int i = 0; i < n - 2; ++i) {
     c = a + b;
     b = a;
     a = c;
   }
   return a;
}
int recursive_fib(int n) {
  if (n <= 2) {
    return 1;
  }
  return recursive_fib(n - 1) + recursive_fib(n-2);
}

В обеих реализациях я предположил правильный ввод, т.е. n> = 1. Первый код намного длиннее, но его сложность O (n), то есть линейная, а вторая реализациякороче, но имеет экспоненциальную сложность O (fib (n)) = O (φ ^ n) (φ = (1+√5)/2) и, следовательно, намного медленнее.Можно улучшить рекурсивную версию, введя запоминание (т. Е. Запоминание возвращаемых значений функции, которую вы уже вычислили).Обычно это делается путем введения массива, в котором вы храните значения.Вот пример:

int mem[1000]; // initialize this array with some invalid value. Usually 0 or -1 
               // as memset can be used for that: memset(mem, -1, sizeof(mem));
int mem_fib(int n) {
  if (n <= 2) {
    return mem[n] = 1;
  }
  if (mem[n-1] == -1) {
    solve(n-1);
  }
  if (mem[n-2] == -1) {
    solve(n-2);
  }
  return mem[n] = mem[n-1] + mem[n-2];
}

Здесь сложность рекурсивного алгоритма линейна, как итеративное решение.Решение, которое я представил выше, является нисходящим подходом для динамического программирования решения вашей проблемы.Восходящий подход приведет к чему-то очень похожему на решение, которое я представил как итеративное.Есть много статей о динамическом программировании, в том числе в википедии

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

Надеюсь, этот ответ поможет.

Answer 2

Конкретный рекурсивный алгоритм для расчета ряда фибанокков менее эффективен. Рассмотрим следующую ситуацию нахождения fib (4) с помощью рекурсивного алгоритма

                int fib(n) :
                        if( n==0 || n==1 )
                            return n;
                        else
                            return fib(n-1) + fib(n-2)

Теперь, когда вышеуказанный алгоритм выполняется для n = 4

                            fib(4)

                    fib(3)             fib(2)

                fib(2)   fib(1)     fib(1)   fib(0)

             fib(1)  fib(0) 

Это дерево. Это говорит о том, что для вычисления fib (4) вам нужно вычислить fib (3) и fib (2) и т. Д.

Обратите внимание, что даже для небольшого значения 4, fib (2) рассчитывается дважды, а fib (1) - трижды. Это количество дополнений растет для больших чисел.

Существует предположение, что число сложений, необходимых для вычисления fib (n), равно

                     fib(n+1) -1

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

Итерационный алгоритм для рядов Фибоначчи значительно быстрее, так как он не включает вычисления избыточных вещей.

Это может быть не один и тот же случай для всех алгоритмов.

Answer 3

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

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

Answer 4

Да, каждый итерационный алгоритм может быть преобразован в рекурсивную версию и наоборот.Один способ - передать продолжения, а другой - реализовать структуру стека.Это делается без увеличения сложности времени.

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

Answer 5

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