斐波那契 算法优化

斐波那契 即是 兔子数列

一对兔子,第一个月没有繁殖能力，所以是一对
第二个月，进入成熟期，仍然是一对
第三个月，兔子1生了一对兔子，于是有两队
第四个月，兔子1又生兔子3
第五个月，兔子1又生兔子4，而兔子2生兔子5
第六个月，依此类推...
得到的数列为 1,1,2,3,5 ,8,13 ,21...

递归表达式:
F(n) =

n=1, 1
n=2, 1
n>2, F(n-1)+F(n-2)

一般递归法：

Fib(int n){
if(n<1){
  return -1;
}
if (n==1|| n==2)
  return 1;
return Fib(n-1)+Fib(n-2);
}

递归我们都知道，一般在时间复杂度上表现不佳

改进2:

仔细观察，斐波那契在计算中，每一项都是前两项的值相加。 如果对其进行记录，下次加法即可，不需要递归调用 前两项了
利用一个数组存储，因为下标存储，已经获值比较方便。

Fib(int n){
if(n<1)
  return -1
int *a = new int[n]
a[0] = 1 //记录最开始的两个值
a[1] = 1
for (i  = 2;i<n;i++){
  a[i] = a[i-1]+a[i-2]
return a[n-1];
}
}
很明显，该时间复杂度 为 O(n),不仅无需采用递归，
在空间复杂度上也为 O(n)，相比递归时间复杂度降低到了多项式阶

改进3:
但是我们很容易又发现一个问题，采取数组，除了每次使用前两项，到第4，5，6.....项，前边的 1, 2, 3 ...项都不需要了，放着也会造成空间浪费。而且我们最终的目的是 获取 第 n 个斐波那契数的数值。

利用辗转相加法(与欧几里得算法相似
[https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95](https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95))
思路:
每次只要知道前两项的值即可,
假如 
     当前项 s3 = s1+s2
下一项的值  s? = s2 + s3
next       s?? = s3 + s?

那么：(括号内容只为了容易理解)
     新值 = 第前两项+ 第前一项
     s2(1) =   s1 +   s2
next s2(2) =  s1 + s2(1)
next s2(3) =  s1 + s2(2)
.....
每次for循环, 加法产生的 新的s2 都会参与到下次 加法计算
解决了 第前一项 的记录，可以观察到 s1 每次也都会参与 计算
此时也只要利用s1对 上一个计算的 s2做一个保存(第前两项) ，然后进行辗转

新值 = 第前两项+ 第前一项
s2(1) = s1 + s2
 s1   =  s2(1) - s1
也就是说
本次加法产生的  s2(1) 作为下一次计算的  s2
上次计算的 s2 作为 本次计算的 s1 (s2(1) -s1)

Fib(int n){
if(n<1)
  return -1
if (n==1|| n==2)
  return 1
s1 =1
s2 = 1
for (i  = 2;i<n;i++){
  s2 = s1+s2
  s1 = s2-s1
}
return s2;
}

虽说 时间复杂度不变，但是空间复杂度得到了极大的缩小O(1).