前端时间火了一部高分悬疑日剧《轮到你了》
此剧讲的是温柔的妻子菜奈和天真浪漫的丈夫翔太,是一对有15岁年差的姐弟恋夫妇,而且他们也是一对推理迷。他们刚搬到东京都内的高级公寓,参加了业主委员会的活动:交换杀人游戏即每个人写下想杀的人,通过抽签的方式去交换杀人,来摆脱社会关系的嫌疑
。 结果弄假成真,真的出现了杀人事件,公寓里所有的居民都开始陷入噩梦之中,精彩的推理谜题也随之展开。
可以理解为真人版狼人杀。
剧里的黑岛长了张初恋脸,温柔、耐看,笑起来很迷人。
她的爱好是数学,尤其迷恋“斐波那契”...
然后我们就开始今天的主题:斐波那契数列
斐波那契数列
斐波那契数列指的是这样一个数列 :
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584...
递推方法定义它:
F(1)=1,
F(2)=1,
F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)
这个数列从第3项开始,每一项都等于前两项之和。
也叫:黄金分割数列、兔子(繁殖)数列。
当n趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618
或者说后一项与前一项的比值小数部分越来越逼近0.618:1÷1=1,1÷2=0.5,2÷3=0.666...,3÷5=0.6,5÷8=0.625…………,55÷89=0.617977……46368÷75025=0.6180339886…...
越到后面,这些比值越接近黄金比.
斐波那契算法
规律:F(n) = F(n-1) + F(n-2)
1. 递归 -----时间复杂度:O(2^N)
int fiboArithmetic(int n) {
if(n=1) return 1;
if(n=2) return 1;
return fiboArithmetic(n-1)+fiboArithmetic(n-2)
}
这样的递归算法虽然只有简单的几行,但是效率却很低。
为什么呢?
因为每次的展开都要把当前的已知项再拆分成当前数目的两倍
例如:要得到F(10)之前得先得到F(9)、F(8),那么得到F(9)之前得先得到F(8)、F(7)……如此递归下去
需要计算2^N-1次
所以斐波那契的递归算法时间复杂度为2^N
2.非递归 --- 时间复杂度为O(N),空间复杂度为O(N)
思路:创建一个数组,每次将前两个数相加后直接赋给后一个数
有N个数就创建一个包含N个数的一维数组,所以空间复杂度为O(N);
由于只需从头向尾遍历一边,时间复杂度为O(N)
void fbiArray(int n) {
int i;
int *arr[n];
arr[0] = 0;
arr[1] = 1;
printf("%d %d ", arr[0], arr[1]);
for(i = 2; i < n; i++) {
arr[i] = arr[i - 1] +arr[i - 2];
printf("%d ", arr[i]);
}
}
3.非递归 ---时间复杂度为O(N),空间复杂度为O(1)
思路:借助两个变量 firstNum 和 secondNum ,每次将 firstNum 和 secondNum 相加后得resultNum,再将 secondNum 赋给 firstNum ,resultNum 赋给 secondNum ,如此循环。
int fibo3(int n)
{
if (n < 2) {
return n;
}
int firstNum = 0;
int secondNum = 1;
int resultNum;
for(int i = 2 ; i <= n; i++){
resultNum = firstNum + secondNum;//前两数相加之和
firstNum = secondNum;
secondNum = resultNum;
}
return resultNum;
}
时间复杂度是指执行这个算法所需要的计算工作量;
空间复杂度是指执行这个算法所需要的内存空间。
时间和空间(即寄存器)都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少
最坏情况下的时间复杂度称最坏时间复杂度, 一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长
递归使用的是选择结构,而迭代使用的是循环结构.