写点什么

算法 | 详解斐波那契数列问题

作者:甜点cc
  • 2022-10-24
    河南
  • 本文字数:2208 字

    阅读完需:约 7 分钟

等比数列求和,如求,该函数属于爆炸增量函数,如果采用常规运算,则要考虑算法的时间复杂度。

算法知识点

  • 斐波那契数

  • 动态规划(拆分子问题;记住过往,减少重复计算)

算法题目

假设第 1 个月有 1 对初生的兔子,第 2 个月进入成熟期,第 3 个月开始生育兔子,而 1 对成熟的兔子每月会生 1 对兔子,兔子永不死去..…那么,由 1 对初生的兔子开始,12 个月后会有多少对兔子呢?

做题思路


这个数列有如下十分明显的特点:从第 3 个月开始,,而。因此,前面相邻两项之和便构成后一项,换言之:


斐波那契数如下:

1 ,1 ,2 ,3 ,5 ,8, 13 ,21 ,34 ......

递归表达式


根据递归表达式,初步的算法代码如下:


const fbn = (n) => {  if (n == 1 || n == 2) {  return 1  } else {  return fbn(n-2) + fbn(n-1)  }}
复制代码


让我们看一下上面算法的时间复杂度,也就是计算的总次数

时间复杂度

时间复杂度算的是最坏情况下的时间复杂度


n=1时,T(n)=1n=2时,T(n)=1;n=3时,T(n)=3; //调用Fib1(2)和Fib1(1)并执行一次加法运算(Fib1(2)+Fib1(1))
复制代码


当 n>2 时需要分别调用fbn(n-1)fbn(n-2)


,并执行一次加法运算,换言之:



所以,


问题来了,怎么判断T(n)属于算法时间复杂度的哪种类型呢?

方法一:

画出递归树,每个节点表示计算一次



一棵满二叉树节点总数就和树的高度呈指数关系


递归树 F(n)里面存在满二叉树,所以时间复杂度是指数阶的

方法二:

使用公式进行递推



因为时间复杂度算的是最坏情况下的时间复杂度,所以计算第一个括号内的即可


即:,时间复杂度是指数阶

算法改进

降低时间复杂度

不难发现:上面基于递归表达式的算法,存在大量的重复计算,增大了算法的时间复杂度,所以我们可以做出如下改进,以减少时间复杂度


// 利用数组记录过往的值,直接使用,避免重复计算const fbn2 = (n) => {  let arr = new Array(n + 1); // 定义 n + 1 长度的数组  arr[1] = 1;  arr[2] = 1;  for (let i = 3; i <= n; i++) {    arr[i] = arr[i - 1] + arr[i - 2]  }  return arr[n]}
复制代码


很显然上面算法的时间复杂度是,时间复杂度从指数阶降到了多项式阶。


由于上面算法使用数组记录了所有项的值,所以,算法的空间复杂度变成了,我们可以继续改进算法,来降低算法的空间复杂度

降低空间复杂度

采用临时变量,来迭代记录上一步计算出来的值,代码如下:


const fbn3 = (n) => {  if (n === 1 || n === 2) {    return 1;  }  let pre1 = 1 // pre1,pre2记录前面两项  let pre2 = 1  let tmp = ''
for (let i = 3; i <= n; i++) { tmp = pre1 + pre2 // 2 pre1 = pre2 // 1 pre2 = tmp // 2 } return pre2}
复制代码


使用了三个辅助变量,时间复杂度还是,空间复杂度降为

测试算法计算时间

// 斐波那契数列// 1 ,1 ,2 ,3 ,5 ,8, 13 ,21 ,34 ......
const fbn = (n) => { if (n == 1 || n == 2) { return 1 } else { return fbn(n-2) + fbn(n-1) }}console.time('fbn')console.log('fbn(40)=', fbn(40))console.timeEnd('fbn')
// 利用数组记录过往的值,直接使用,避免重复计算const fbn2 = (n) => { let arr = new Array(n + 1); // 定义 n + 1 长度的数组 arr[1] = 1; arr[2] = 1; for (let i = 3; i <= n; i++) { arr[i] = arr[i - 1] + arr[i - 2] } return arr[n]}
console.time('fbn2')console.log('fbn2(40)=', fbn2(40))console.timeEnd('fbn2')
const fbn3 = (n) => { if (n === 1 || n === 2) { return 1; } let pre1 = 1 // pre1,pre2记录前面两项 let pre2 = 1 let tmp = ''
for (let i = 3; i <= n; i++) { tmp = pre1 + pre2 // 2 pre1 = pre2 // 1 pre2 = tmp // 2 } return pre2}
console.time('fbn3')console.log('fbn3(40)=', fbn3(40))console.timeEnd('fbn3')
复制代码


测试结果如下:


fbn(40)= 102334155fbn: 667.76msfbn2(40)= 102334155fbn2: 0.105msfbn3(40)= 102334155fbn3: 0.072ms
复制代码

小结

能不能继续降阶,使算法的时间复杂度更低呢?实质上,斐波那契数列的时间复杂度还可以降到对数阶,好厉害!!!后面继续探索吧


算法作为一门学问,有两条几乎平行的线索:


  1. 数据结构(数据对象):数、矩阵、集合、串、排列、图、表达式、分布等。

  2. 算法策略:贪心策略、分治策略、动态规划策略、线性规划策略、搜索策略等。


这两条线索是相互独立的:


  • 对于同一个数据对象上不同的问题(如单源最短路径和多源最短路径),就会用到不同的算法策略(如贪心策略和动态规划策略);

  • 对于完全不同的数据对象上的问题(如排序和整数乘法),也许就会用到相同的算法策略(如分治策略)。




我是 甜点 cc


热爱前端,也喜欢专研各种跟本职工作关系不大的技术,技术、产品兴趣广泛且浓厚,等待着一个创业机会。本号主要致力于分享个人经验总结,希望可以给一小部分人一些微小帮助。


希望能和大家一起努力营造一个良好的学习氛围,为了个人和家庭、为了我国的互联网物联网技术、数字化转型、数字经济发展做一点点贡献。数风流人物还看中国、看今朝、看你我。

发布于: 刚刚阅读数: 3
用户头像

甜点cc

关注

看见另一种可能 2020-04-30 加入

欢喜勇猛

评论

发布
暂无评论
算法 | 详解斐波那契数列问题_JavaScript_甜点cc_InfoQ写作社区