算法：斐波那契数列 Fibonacci

斐波那契数列 Fibonacci

斐波那契数列是这样的数列：

0、1、1、2、3、5, 8、13、21、34 ……

下一项是上两项的和。

2 是上两项的和（1+1） 3 是上两项的和（1+2）、 5 是（2+3）、 依此类推！

更多有意思的介绍可以见参考链接；

算法

1. 直接递归

初步想法就是采用递归的方式去实现 fib(n) = fib(n-1) + fib(n-2)

def fib(n):
 if n == 1:
  return 0
 if n == 2:
  return 1
 return fib(n-1) + fib(n-2)

以n=6为例，可以看到fib(6)分解为fib(5)、fib(4)， fib(5)分解为fib(4)、fib(3), fib(4)分解为fib(3)、fib(2), 等等

可以看到这个过程中会有重复计算的过程；相当于每个fib(k)都要被计算2次， n个数字，则需要计算2^n次，所以时间复杂度为O(2^n); 由于采用递归的方式，需要用栈保存每次递归的结果，然后一直到头后再反向得到结果，需要用O(n)的空间去存储fib(n)、fib(n-1)..., fib(1)， 所以空间复杂度为O(n);

2. 递归+hashmap

那么借助于**空间换时间**的思想，使用hashmap去保存每次计算到的fib(k),需要用到fib(k)时候，直接去hashmap中查就行，不用重复计算；

def fib(n, memorize={1:0, 2: 1}):
 if n in memorize:
  return memorize[n]
 memorize[n] = fib(n-1, memorize) + fib(n-2, memorize)
 return memorize[n]

时间复杂度为O(n), 空间复杂度为O(n)

3. 递归+两变量

相较于上面的每个fib(i)都保存，可以只保留

从头开始算，可以只保留最近的两个元素的值就可以的

def fib(n):
 lastTwo = [0, 1]
 counter = 3
 while counter <= n:
  nexFib = lastTwo[0] + lastTwo[1]
  lastTwo[0] = lastTwo[1]
  lastTwo[1] = nexFib
  counter += 1
 return lastTwo[1] if n > 1 else lastTwo[0]

时间复杂度为O(n), 空间复杂度为O(1)

参考

• https://www.shuxuele.com/numbers/fibonacci-sequence.html