为什么这个记忆功能不能在线性时间内运行？

Question

我试图在递归的fibonacci函数中使用数组实现memoisation,fibmem()期望runninng时间以O(n)的形式出现.最初,它看起来好像我拥有它,因为它比常规的递归fibonacci函数运行要快得多.(红色是正常的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操作扫描列表中,并线性时间,但你做的是完全错误的.

你的memo意志将被填满[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...].因此,当n例如40,并且你正在检查时40 not in memo,它将总是失败,因为40不是斐波纳契数.显然,你的意思是要检查第40个Fibonacci数是否已经计算过,但这根本不是你实际检查的数字.而是检查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:做它应该做的事情(因为它检查键,而不是值).这也具有不受限制的优点.