代码之家 › 专栏 › 技术社区 › Eugene Yarmash

动态编程:递归+记忆vs循环+列表

memoization dynamic-programming recursion python

Eugene Yarmash · 技术社区 · 6 年前

文件 @functools.lru_cache 提供了使用缓存实现动态编程技术计算斐波那契数的示例:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

我见过这种方法用于解决各种编程难题。它的时间/空间复杂性是否与“标准”迭代动态规划方法相同,例如:

def fib(n):
    if n < 2:
        return n
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(2 , n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

另外,使用递归方法有什么缺点吗?

2 回复 | 直到 6 年前

MBo 6 年前

它应该和 memoization (自上而下)一种动态编程。

逐步填充表的迭代方法(自底向上动态编程)可能有稍微不同的复杂性,因为memoization只记住构建最终解决方案所需的参数集。

对于fibbonacci或阶乘示例,这种差异并不重要,但对于具有稀疏子问题表的任务(当很难预测以后将使用哪些条目时),这种差异可能会发生。

MSeifert 6 年前

下面将比较您所显示的函数。一般来说,这些观察结果不一定适用于任何计算斐波那契数的递归或迭代方法,但仅限于问题中所示的实现。

时间复杂性:

第一次呼叫

递归方法:o(n)
迭代法:o(n)

后续通话

递归方法:o(1)
迭代法:o(n)

常数因子

常数因子可能完全不同。很可能(第一次调用)迭代方法比递归方法更快,尽管两者都是 O(n) . 这只是一个猜测,根据我的经验(不是实际的测试),列表索引比调用函数快得多。

内存复杂性:

两者都需要O(N)额外的内存,但是递归方法将保留内存(因此它是永久分配的),而迭代方法将在函数完成后释放内存。

其他差异

python的递归限制。当时间太长,缓存没有填满时,递归方法就会因为这个限制而失败,例如 fib(500) . 列表索引没有这样的限制(内存不足时除外)。

推荐文章

Justin Haddock · 动态规划Python路径算法

7 年前

Pal Jereh · 形成字符串的最小路径

7 年前

asndonsadoasndo231213 · “查找具有k-唯一字符的最长子串”的时间复杂度?

7 年前

FunnyBuzer · 排列n大小数组的所有元素,使输出数组首先具有所有负元素,然后是零和正元素,无需排序

7 年前

user724861 · 二叉树上的动态规划:在有限的边缘容量下最大化数据传输

7 年前

Marked as Duplicate · 使用集合中尽可能多的数字求和

7 年前

Reddy90 · 计算二进制表示形式正好需要数字1的数字

7 年前

daniel · java—如何避免将全局外部变量作为递归函数的输出

7 年前

ng.newbie · TopCoder中的示例违反了约束

7 年前

Mohamed Benkedadra · 数组中每个元素的递归

7 年前