python - 为什么这个内存功能不能在线性时间内运行？

Question

我尝试在递归斐波那契函数中使用数组实现内存，fibmem() 期望运行时间为 O(n)。最初，它看起来好像我有它，因为它比常规的递归斐波那契函数运行起来要快得多。 (红色是常规 fib()，绿色是 fibmem())

但进一步检查，(fibmem() 由红色表示)

它看起来好像 fibmem() 在 O(someconstant^n) 时间内运行。这是代码:

memo = [0] * 100 #initialise the array
argument = sys.argv[1]

def fibmem(n):

        if n < 0:
            return "NO" 
        if n == 0 or n == 1:
            memo[n] = 1
            return memo[n]
        if n not in memo:
            memo[n] = fibmem(n-1) + fibmem(n-2)
        return memo[n]

现在我可以通过这种方式使用字典而不是数组让 fibmem() 在 O(n) 时间内运行:

memo = {0:1, 1:1}

argument = sys.argv[1]

def fibmem(n):

        if n not in memo:
            memo[n] = fibmem(n-1) + fibmem(n-2)
        return memo[n]

但我认为我使用数组的实现是相似的。我只是不明白为什么 fibmem() 的数组实现以指数时间运行。这是怎么回事？我将如何解决问题？

Answer 1

真正的问题不在于in 运算符扫描列表并花费线性时间，而是你这样做完全错误 .

您的备忘录将填充[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...]。因此，例如当 n 为 40 时，您正在检查 40 not in memo，它只会总是失败，因为 40 不是一个斐波那契数。显然，您的意思是检查是否已经计算出第 40 个斐波那契数，但这根本不是您实际检查的内容。您要检查 40 是否是(已计算的)斐波那契数。

因此，只有当 n 本身恰好是斐波那契数时，例如 34，您才会获得快捷方式。但是直到 55，您永远不会获得任何此类快捷方式，有效地禁用了您的内存完全(在这些范围内)。这就是为什么你会在那里得到指数行为，就像之前的非记忆化版本一样。

另请注意，n=35 和 n=36 之间的曲线明显中断。这不仅仅是侥幸，正是因为 34 是斐波那契数列。 n=36 的情况可以追溯到 n=35 和 n=34，因为 n=34 是一个即时捷径，只有 n=35 部分涉及实际工作。这就是为什么 n=36 花费的时间与 n=35 几乎完全相同(这是侥幸，当您测量它时花费的时间略少)。

而不是 if n not in memo: 你应该检查 if memo[n] == 0: 或 if not memo[n]:.

或者改为使用字典:memo = {}。然后你的 if n not in memo: 做它应该做的(因为它检查键，而不是值)。这也有不受限制的优点。