斐波那契算法浅聊

466 阅读4分钟

前端时间火了一部高分悬疑日剧《轮到你了》

UTOOLS1573543299978.png

此剧讲的是温柔的妻子菜奈和天真浪漫的丈夫翔太,是一对有15岁年差的姐弟恋夫妇,而且他们也是一对推理迷。他们刚搬到东京都内的高级公寓,参加了业主委员会的活动:交换杀人游戏即每个人写下想杀的人,通过抽签的方式去交换杀人,来摆脱社会关系的嫌疑。 结果弄假成真,真的出现了杀人事件,公寓里所有的居民都开始陷入噩梦之中,精彩的推理谜题也随之展开。 可以理解为真人版狼人杀。

剧里的黑岛长了张初恋脸,温柔、耐看,笑起来很迷人。

UTOOLS1573639800019.png

她的爱好是数学,尤其迷恋“斐波那契”...

然后我们就开始今天的主题:斐波那契数列

斐波那契数列

斐波那契数列指的是这样一个数列 :

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;
}

时间复杂度是指执行这个算法所需要的计算工作量;

空间复杂度是指执行这个算法所需要的内存空间。

时间和空间(即寄存器)都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少

最坏情况下的时间复杂度称最坏时间复杂度, 一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长

递归使用的是选择结构,而迭代使用的是循环结构.