斐波那契数列计算效率问题

Question

我写了一个函数，计算斐波那契数列的第n项数值

def fib_n(x):
s=[0,1]
if x<=1:
    return s[x]
else:
    k=2
    while (k<=x):
        m=s[k-2]+s[k-1]
        s.append(m)
        k=k+1
    return s[x]
        

但是报出占用的空间比较大，有另外一种计算方法是：

 def Fibonacci(self, n):
    # write code here
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n >= 3:
        s = []*n
        s.append(1)
        s.append(1)
        for i in xrange(2,n):
            s.append(s[i-1]+s[i-2])
        return s[n-1]

我想问下，第二种为什么占用空间比较小。
我知道这个问题可能比较简单，如果哪位愿意指教，可以告诉我一下，这是哪一部分知识缺乏？

Answer 1

首先你写的函数时间空间效率不是很高。
至于空间的问题我暂时看出来的是第一种总会创建s变量，第二种在n<3的情况下不会。
我的建议是这种写法(Python3)。

from functools import lru_cache
@lru_cache(maxsize = 10000)
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

其中lru_cache是Python自带的利用LRU算法的缓存模块，意思就是算过的fib(n)(最近计算过的10000个之内)会缓存下来，直接使用，整体上和使用循环效率一致。

Answer 2

我觉得其他人都只是提供更好的计算斐波那契的方法，却不是回答 第二种为什么占用空间比较小？的啊。

感谢 起风了 对 s = []*n 指出的错误。s = []*n 其实与 s = [] 等价。

以下是我测试的代码:

import sys
def fib_n(x):
    s = [0, 1]
    if x <= 1:
        return s[x]
    else:
        k = 2
        while (k <= x):
            m = s[k - 2] + s[k - 1]
            s.append(m)
            k = k + 1
        print("fib_n: %s len=%s" % (sys.getsizeof(s), len(s)))
        return s[x]

def Fibonacci(n):
    # write code here
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n >= 3:
        s = []*n
        s.append(1)
        s.append(1)
        for i in range(2,n):
            s.append(s[i-1]+s[i-2])
        print("Fibonacci: %s len=%s" % (sys.getsizeof(s), len(s)))
        return s[n-1]

fib_n(90)    # fib_n: 792 len=91
Fibonacci(90)# Fibonacci: 792 len=90

第二种占用空间更大。但是第二种的数组元素个数明明是更小的啊，这是为什么？
这是因为后面两句 s.append(1) 会占用一些空间：

print(sys.getsizeof([1,1])) # 80
s = []
s.append(1)
s.append(1)
print(sys.getsizeof(s))    # 96

python中数组的实现是类似 C++ 中 vector 的。空间和随元素占用而增长，因此会有一些空间是还没被利用的，比如一个仅为 3 个元素的宿主，它的内存上表现是：

[1, 2, 3, NULL, NULL, NULL, NULL]

按照增长规则:

new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

比如 [1,2] 下一个 append 就需要3个空间，就将 newsize = 3 代入规则，得出数组新申请的空间。
第一种增长的空间分别为: 2, 6, 10, 18, 27, 37, 48, 61, 75, 91
第二种增长的空间分别为: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, 106
因此，不一定是哪种方法占的空间更低。例如，当 n = 80 时，第二种方法占用空间就更低。

Answer 3

我觉得内存开销在数量级上没啥区别，s = []*n这句话好像也是多余的，没什么意义。不如用generator：

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b

for i in fib():
    print(i)
    if i > 1024:break

Answer 4

别用递归，会造成会多浪费的计算。 详情 请查阅 尾递归！！！！！ 重要的事情说三遍 尾递归 尾递归 尾递归。

Answer 5

关键两点：
1.别用尾递归，计算的n的值稍微大一点就会爆栈。
2.python中数组的添加元素的过程
参看链接：http://hyry.dip.jp/tech/slice...
额外分配的内存与数组的大小成正比
建议了解下底层数组的实现（为什么占用空间会比较大），以及计算机程序大致是怎么运行的（为什么尾递归会出现爆栈问题）。