【Day34】[演算法]-费波那契数列Fibonacci Sequence

之前在递回的篇章有介绍过费波那契数列，是使用递回的方式实作，但是从下面递回的树状图来看，会发现有很多重复的节点，递回的深度越深，重复计算的节点也就越多，甚至会出现RecursionError的情况，而这样的时间复杂度为O(2^n)。

因此可以将会重复计算的部分暂存起来，避免重覆计算来增加处理效能。

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    seq = [0 for _ in range(n + 1)]
    seq[0] = 0
    seq[1] = 1
    for i in range(2, n + 1):
      seq[i] = seq[i-1] + seq[i-2]
    return seq[n]

fibonacci(8)#21

• 建立一个seq列表
• seq[i]为F(i)的值，可以说seq[i] = seq[i-1] + seq[i-2]
• 把seq[0]为0、seq[1]为1
• 用回圈计算i=2到n+1时，得出seq[i]的结果，储存於seq列表中被使用
• 最後算出来的seq[n]，就是F(n)的值

透过上面的方式，可以发现真正被计算到的只剩下橘色部分，蓝色框为已经被储存在seq列表中，不需要重复计算，时间复杂度变为O(n)

根据上述方式，空间复杂度为O(n)，但还可以有更进阶的方式来节省空间。

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    a = 0
    b = 1
    for i in range(2, n+1):
        c = a + b
        a = b
        b = c
    return b

fibonacci(8)#21

• 开始的前两项a与b，为0与1
• 後一项c是前两项的加总
• 只需要对a和b不断重新赋值

空间复杂度就能从原本的O(n)变成O(1)。