对于记忆的递归与迭代，Big O表示法是否相同? [英] Is the Big O notation the same for memoized recursion versus iteration?

问题描述

我在这里举个简单的例子

I am using a simple example off the top of my head here

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

或者具有递归功能且具有记忆功能的函数与动态编程的功能，在动态函数中，您可以遍历数组并填充值等.

Or functions that are recursive and have memoization vs. dynamic programming where you iterate over an array and fill in values, etc.

我知道有时递归不好，因为您可能会耗尽堆(或堆栈?)的内存(尾递归?)，但这是否会影响O表示法?

I know that sometimes recursion is bad because you can run out of memory (tail recursion?) with the heap (or stack?), but does any of this affect O notation?

递归存储算法与迭代版本的O表示法/速度是否相同?

Does a recursive memoized algorithm have the same O notation / speed as the iterative version?

推荐答案

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

Generally when considering an algorithm's complexity we would consider space and time complexity separately.

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

Two similar algorithms, one recursive, and one converted to be not recursive will often have the same time complexity, but differ in space complexity.

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

In your example, both factorial functions are O(n) time complexity, but the recursive version is O(n) space complexity, versus O(1) fort he iterative version.

这种差异不是普遍的.内存占用空间，有时占用的空间与递归版本使用的堆栈空间相当甚至更大.

This difference isn't universal. Memoization take space, and sometimes the space it takes up is comparable or even greater than the stack space a recursive version uses.

这篇关于对于记忆的递归与迭代，Big O表示法是否相同?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！