小编img*_*mad的帖子

我试图在递归的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) + …

我有一个简单的Fibonacci函数,它使用memoisation,它本身就可以正常工作.但是,当我想使用timeit计时时,我得到"NameError:全局名称'备忘录'未定义",即使它是.

#!/usr/bin/python

import sys
import timeit

memo = [0] * 100

def fibmem(n,memo):
    #function things

for x in range(1,40):

    mytime2 = timeit.Timer('fibmem('+str(x)+', memo)','from __main__ import fibmem')
    delta2 = mytime2.timeit(1)
    print str(x) + ' ' +str(delta2)
    memo[:] = []

我已经尝试过查找它可能是什么,但大多数答案涉及到包括from __main__ import,这不是问题.我确定它仍然与范围有关,但我对时间非常新,所以我不知道.