python - 查找递归函数的时间和空间复杂度

Question

我在分析递归函数的时间和空间复杂性时遇到困难:

考虑:

def power(a, n):
    if n==0:
        return 1
    else:
        return a*power(a, n-1)

当找到这个的时间复杂度时:我认为 T(n) = c + T(n-1) 其中 c 是乘法的常数成本。

这可能会导致:c*n 成本，即线性成本 O(n)。但递归的成本通常呈指数级增长。

另外，考虑这个函数:

def power(a,n):
    if n==0:
        return 1
    if n%2 ==0:
        return power(a*a, n//2)
    else:
        return a*power(a*a, n//2)

上面的函数将一直运行到:T(n) = c + T(n/2) 这意味着成本将为 c*log(n) 表示 log(n) 复杂度。

如果分析正确，那么递归看起来和迭代算法一样快，那么开销从何而来，有指数递归算法吗？

Answer 1

递归的复杂度不是指数级的。事实上有一个定理，每个递归算法都有一个迭代模拟，反之亦然(可能使用额外的内存)。有关如何执行此操作的说明，请参阅 here例如。还可以查看维基百科中比较 recursion and iteration 的部分.

当递归函数在其某些流程中多次调用自身时，您可能会以指数复杂度结束，就像著名的斐波那契数列示例一样:

def fib(n):
   if n < 2:
       return 1
   return fib(n - 1) + fib(n - 2)

但这并不意味着没有更快的递归实现。例如使用 memoization您可以将其降低到线性复杂度。

仍然递归实现确实有点慢，因为在进行递归调用时应存储堆栈帧，并在返回值时应将其恢复。