使用 O(1) space 在 python 中自下而上的斐波那契

Question

我想用 O(1) space 写一个自下而上的斐波那契数列。我的问题是 python 的递归堆栈限制了我测试大量数据。有人可以为我所拥有的提供替代或优化吗？这是我的代码：

def fib_in_place(n):
    def fibo(f2, f1, i):
        if i < 1:
            return f2
        else:
            return fibo(f1, f2+f1, i -1)
    return fibo(0, 1, n)

Answer 1

你可以记忆斐波那契函数以提高效率，但如果你需要一个递归函数，它仍然至少需要 O(n):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

这是我对 Python 问题中主要斐波那契的回答：How to write the Fibonacci Sequence in Python

如果你被允许使用迭代而不是递归，你应该这样做：

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

用法：

>>> list(zip(range(10), fib()))
[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21), (9, 34)]

如果你只想得到第n个数：

def get_fib(n):
    fib_gen = fib()
    for _ in range(n):
        next(fib_gen)
    return next(fib_gen)

和用法

>>> get_fib(10)
55

Answer 2

以这种方式使用递归意味着您使用的是 O(N) space，而不是 O(1) - O(N) 在堆栈中。

为什么要使用递归？

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b

    return a

Answer 3

尾递归定义很容易变成迭代定义。如有必要，翻转条件，使尾递归调用在 'if' 分支中。

def fibo(f2, f1, i):
    if i > 0:
        return fibo(f1, f2+f1, i -1)
    else:
        return f2

然后将 'if' 变为 'while'，将 return 替换为新参数的解包赋值，并且（可选）删除 'else'.

def fibo(f2, f1, i):
    while i > 0:
        f2, f1, i = f1, f2+f1, i -1
    return f2

有了迭代，就不需要嵌套定义了。

def fib_efficient(n):
    if n < 0:
        raise ValueError('fib argument n cannot be negative')
    new, old = 0, 1
    while n:
        new, old = old, old+new
        n -= 1
    return new

本地名称'new'和'old'指的是斐波那契使用生物繁殖来激发数列。然而，这个故事更适用于酵母细胞而不是兔子。旧的、成熟的酵母细胞通过萌芽出新的、未成熟的细胞来繁殖。（该函数在印度的原始来源似乎是 Virahanka 计算数字的一种方法，它可以从 1 拍和 2 拍音节的有序序列中制作出具有 n 拍的梵语诗行。）

Answer 4

为什么要使用迭代？

def fib(n):
    phi_1 = (math.sqrt(5) + 1) / 2
    phi_2 = (math.sqrt(5) - 1) / 2
    f = (phi_1**n - phi_2**n) / math.sqrt(5)
    return round(f)

代数结果准确； round 操作仅允许数字表示不准确。

使用 O(1) space 在 python 中自下而上的斐波那契

bottom up fibonacci in python using O(1) space

python

recursion

fibonacci