迭代和递归版本的算法是否具有相同的时间复杂度？

Question

比方说,例如,Fibonacci系列的迭代和递归版本.他们有相同的时间复杂性吗？

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)因此慢得多.可以通过引入memoization来改进递归版本(即记住已经计算过的函数的返回值).这通常通过引入存储值的数组来完成.这是一个例子:

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

因此，这种重复是导致这种特定算法性能下降的原因。

Fibonacci级数的迭代算法要快得多，因为它不涉及计算多余的事物。

但是，对于所有算法而言，情况可能都不相同。