感謝 起風(fēng)了 對(duì) s = []*n 指出的錯(cuò)誤。s = []*n 其實(shí)與 s = [] 等價(jià)。

以下是我測(cè)試的代碼:

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

第二種占用空間更大。但是第二種的數(shù)組元素個(gè)數(shù)明明是更小的啊，這是為什么？
這是因?yàn)楹竺鎯删?s.append(1) 會(huì)占用一些空間：

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

python中數(shù)組的實(shí)現(xiàn)是類似 C++ 中 vector 的?？臻g和隨元素占用而增長(zhǎng)，因此會(huì)有一些空間是還沒(méi)被利用的，比如一個(gè)僅為 3 個(gè)元素的宿主，它的內(nèi)存上表現(xiàn)是：

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

按照增長(zhǎng)規(guī)則:

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

比如 [1,2] 下一個(gè) append 就需要3個(gè)空間，就將 newsize = 3 代入規(guī)則，得出數(shù)組新申請(qǐng)的空間。
第一種增長(zhǎng)的空間分別為: 2, 6, 10, 18, 27, 37, 48, 61, 75, 91
第二種增長(zhǎng)的空間分別為: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, 106
因此，不一定是哪種方法占的空間更低。例如，當(dāng) n = 80 時(shí)，第二種方法占用空間就更低。