python - 内存递归与迭代的大 O 表示法是否相同？

Question

我在这里使用了一个简单的例子

function factorial(n)
   if n==1 return 1
   else return n*factorial(n-1)

function factorial(n)
    result = 1
    for i = 1 to n
        result *= n
    return result

或者递归函数和具有内存功能的函数与动态编程相比，您可以在其中迭代数组并填充值等。

我知道有时递归很糟糕，因为堆(或堆栈？)可能会耗尽内存(尾递归？)，但这会影响 O 表示法吗？

递归内存算法是否具有与迭代版本相同的 O 符号/速度？

Answer 1

一般在考虑算法的复杂度时，我们会分别考虑空间复杂度和时间复杂度。

两种相似的算法，一种是递归的，一种是转换为非递归的，通常时间复杂度相同，但空间复杂度不同。

在您的示例中，两个阶乘函数的时间复杂度均为 O(n)，但递归版本的空间复杂度为 O(n)，而迭代版本的复杂度为 O(1)。

这种差异并不普遍。记忆化占用空间，有时它占用的空间与递归版本使用的堆栈空间相当甚至更大。