相关疑难解决方法(0)

我无法弄清楚为什么以下代码是以fib线性而非指数时间运行的.

def memoize(obj):
    """Memoization decorator from PythonDecoratorLibrary. Ignores
    **kwargs"""

    cache = obj.cache = {}

    @functools.wraps(obj)
    def memoizer(*args, **kwargs):
        if args not in cache:
            cache[args] = obj(*args, **kwargs)
        return cache[args]
    return memoizer

@memoize
def fib(n):
    return n if n in (0, 1) else fib(n-1) + fib(n-2)

例如,fib(100)并没有像我预期的那样完全爆炸.

我的理解是@memoize那套fib = memoize(fib).所以,当你打电话fib(100),看到100是不在缓存中,它会调用obj上100.但这obj是原始的fib功能,所以不应该花费同样长的时间(在第一次评估时),就好像我们根本没有记忆一样？