python – 对于memoized递归与迭代,Big O表示法是否相同？

发布时间：2020-12-20 13:39:40 所属栏目：Python 来源：网络整理

导读：我在这里使用了一个简单的例子 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 或者是递归的函数,并且具有memoization和动态编程,在迭代数组并填充值等等

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

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

或者是递归的函数,并且具有memoization和动态编程,在迭代数组并填充值等等.

我知道有时递归是坏的,因为你可以用堆(或堆栈？)耗尽内存(尾递归？),但这是否会影响O表示法？

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

解决方法

通常,在考虑算法的复杂性时,我们将分别考虑空间和时间复杂度.

两个类似的算法,一个递归,一个转换为非递归,通常具有相同的时间复杂度,但空间复杂度不同.

在您的示例中,两个阶乘函数都是O(n)时间复杂度,但递归版本是O(n)空间复杂度,而O(1)则是迭代版本.

这种差异并不普遍. memoization占用空间,有时它占用的空间与递归版本使用的堆栈空间相当甚至更大.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!