斐波那契 即是 兔子数列
一对兔子,第一个月没有繁殖能力,所以是一对
第二个月,进入成熟期,仍然是一对
第三个月,兔子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).
网友评论