为什么回忆录功能不能在线性时间内运行？

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]

现在我可以用字典而不是数组在O（n）时间内运行fibmem()，方法如下：

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操作符扫描列表并花费线性时间，而是你做的完全是错误的。你知道吗

您的memo将被[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 memo[n] == 0:或if not memo[n]:，而不是if n not in memo:。你知道吗

或者使用字典：memo = {}。然后您的if n not in memo:执行它应该执行的操作（因为它检查键，而不是值）。这也有不受限制的优点。你知道吗

Answer 2

您的问题是，列表上的in操作符从头到尾扫描列表。它不会神奇地知道你在有序地储存东西。你知道吗

你可以用集合来解决这个问题。或者可以使用数组查找检查是否设置了数组值：

memo = [1,1] + [0]*98
def fibmem(n):
    answer = memo[n]

    if answer == 0:
        answer = fibmem(n-1) + fibmem(n-2)
        memo[n] = answer

    return answer