算法的迭代版本和递归版本是否具有相同的时间复杂度？ [英] Do iterative and recursive versions of an algorithm have the same time complexity?

问题描述

例如，斐波那契数列的迭代和递归版本。它们具有相同的时间复杂度吗？

Say, for example, the iterative and recursive versions of the Fibonacci series. Do they have the same time complexity?

推荐答案

答案很大程度上取决于您的实现。对于您给出的示例，有几种可能的解决方案，我想说，实现迭代的天真的方法具有更好的复杂性。这是两个实现：

The answer depends strongly on your implementation. For the example you gave there are several possible solutions and I would say that the naive way to implement a solution has better complexity when implemented iterative. Here are the two implementations:

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 ），因此速度要慢得多。
可以通过引入记忆来改善递归版本（即记住已经计算出的函数的返回值）。这通常是通过引入一个用于存储值的数组来完成的。这是一个示例：

In both implementations I assumed a correct input i.e. n >= 1. The first code is much longer but its complexity is O(n) i.e. linear, while the second implementation is shorter but has exponential complexity O(fib(n)) = O(φ^n) (φ = (1+√5)/2) and thus is much slower. One can improve the recursive version by introducing memoization(i.e. remembering the return values of the function you have already computed). This is usually done by introducing an array where you store the values. Here is an example:

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];
}

在这里，递归算法的复杂度是线性的，就像迭代解决方案一样。我上面介绍的解决方案是自上而下的动态编程解决方案。自下而上的方法将导致非常类似于我作为迭代介绍的解决方案。
关于动态编程的很多文章，包括维基百科

Here the complexity of the recursive algorithm is linear just like the iterative solution. The solution I introduced above is the top-down approach for dynamic programming solution of your problem. The bottom-up approach will lead to something very similar to the solution I introduced as iterative. There a lot of articles on dynamic programming including in wikipedia

根据我在经验中遇到的问题，有些问题很难使用自下而上的方法（即迭代解决方案）解决，而其他问题则很难用自上而下的方法解决。
但是，该理论指出，具有迭代解的每个问题都具有相同的计算复杂性（反之亦然）的递归。

Depending on the problems I have met in my experience some are way harder to be solved with bottom-up approach(i.e. iterative solution), while others are hard to solve with top-down approach. However the theory states that each problem that has an iterative solution has a recursive with the same computational complexity (and vice versa).

希望这个答案会有所帮助。

Hope this answer helps.

这篇关于算法的迭代版本和递归版本是否具有相同的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！