擅长:python、mysql、java
<p>真正的问题不是<code>in</code>操作符扫描列表并花费线性时间,而是你做的完全是错误的。你知道吗</p>
<p>您的<code>memo</code>将被<code>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...]</code>填充。因此,当<code>n</code>例如是40,并且您正在检查<code>40 not in memo</code>,它将总是失败,因为40不是斐波那契数。很明显,你的意思是要检查第40个斐波那契数是否已经计算出来了,但这根本不是你真正要检查的。而是检查40是否是(已经计算过的)斐波那契数。你知道吗</p>
<p>所以只有当<code>n</code>本身恰好是斐波那契数时,才能得到一个快捷方式,例如34。但在55岁之前,你永远不会有这样的捷径,<strong>有效地完全禁用你的记忆(在这些范围内)。这就是为什么会出现指数行为,就像之前的非记忆版本一样。你知道吗</p>
<p>还要注意,n=35和n=36之间曲线的显著中断。这不仅仅是侥幸,这正是因为34是一个斐波那契数。n=36的情况返回到n=35和n=34,因为n=34是一个即时的快捷方式,所以只有n=35部分涉及实际工作。这就是为什么n=36与n=35所用的时间几乎完全相同(它是一种侥幸,当你测量它时,它所用的时间略小于它)。你知道吗</p>
<p>您应该检查<code>if memo[n] == 0:</code>或<code>if not memo[n]:</code>,而不是<code>if n not in memo:</code>。你知道吗</p>
<p>或者使用字典:<code>memo = {}</code>。然后您的<code>if n not in memo:</code>执行它应该执行的操作(因为它检查键,而不是值)。这也有不受限制的优点。你知道吗</p>