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

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

memoization dynamic-programming recursion python

Eugene Yarmash · 技术社区 · 7 年前

文件 @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 回复 | 直到 7 年前

MBo 7 年前

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

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

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

MSeifert 7 年前

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

时间复杂性:

第一次呼叫

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

后续通话

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

常数因子

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

内存复杂性:

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

其他差异

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

推荐文章

Google User · Django管理员在`list_display中未显示`creation_date`字段`

1 年前

user29747013 · 如何创建一个新的数据框架,其中包含原始数据框架中列的聚合列?

1 年前

ÎÎÎ½Î· ÎÎ®Î¹Î½Î¿Ï · Python lxml.html语法错误:使用lxml find时XPATH的谓词无效

1 年前

user29715306 · from_users=和chats=电视节目中的差异

1 年前

Redshoe · 当执行numpy.genfromtxt()时,python是否会读取文件的所有行?

1 年前

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

1 年前

prayner · 更新嵌套字典包含列表中的项

1 年前

Bringo Jr · 我可以在O(n)中解决这个问题吗?

1 年前

Dave · 如何在for循环中修改列表值

1 年前

Shukurullox Komiljonov · 从记录中获得相互和解。使用SQL

1 年前