【面试题】如此高效的斐波那契数列你见过吗?

简介: 递归中经典的题目就是斐波那契数列,而且在面试中,面试官也特别喜欢问你这道题

引出问题


递归中经典的题目就是斐波那契数列,而且在面试中,面试官也特别喜欢问你这道题。


如果换做是你,面试官让你写一个递归函数获取斐波那契数列第n个数的值,想必你的做法是这样的:


    function fibonacci1(n) {  if(n == 1 || n == 2) return 1;  return fibonacci(n - 1) + fibonacci(n - 2)}


    先声明一点,这样的写法是完全正确的,同时这也能体现出递归的优点,那就是代码简洁,但与此同时缺点也非常的明显,那就是效率非常低,不信我们来看个例子


    Q:请求出斐波那契数列中第6个数的值


    我们来分析一下解决该问题时的过程,如下图所示


    30757ac3d47cfa01bc71c00c31ddb242.png


    很明显得看到,递归过程中,有很多值重复求了不止一次,例如 4 和 3 ,若我们要获取得数比6还大的话,重复求值的现象会更加的明显,这无疑是很消耗性能的


    接下来就介绍另一种方式,来提高这个方法的效率


    解决办法


    递归的过程会造成重复求值的现象是因为我们是从第n个数开始往前推导的,而只有第1个数和第2个数是已知的,值为1,所以其它所有的值都要根据它俩来求得。


    所以我们想到的办法就是不妨从前往后推,首先我们可以创建个数组,从第一个数开始,在该数组中记录每个索引位置上的值,代码如下:


      function fibonacci2(n) {  // 记录斐波那契数列 第1个数 到 第n个数 的所有值  let arr = [1, 1]  // 获取n个数之前所有的值,并存储在arr中  for(let i = 2; i < n; i++) {    arr[i] = arr[i - 1] + arr[i - 2]  }    // 直接从arr中返回我们要的值  return arr[n - 1]}


      换个角度来说,我们在求解过程中,将所有求过的值都记录存储了下来,因此不用像递归一样重复求值,所以这是一种非常高效的做法


      效率比较


      我们来比较一下上面两种求取斐波那契数列方法的效率


        // 递归求取的开始时间let start1 = Date.now()// 递归求取第40个数的值console.log(fibonacci1(40))// 递归求取的结束时间let end1 = Date.now()
        // 高效的方法求值的开始时间let start2 = Date.now()// 高效的方法求取第40个数的值console.log(fibonacci2(40));// 高效的方法求值的结束时间let end2 = Date.now()
        console.log(`递归所用时间:${end1 - start1} ms高效的方法所用时间:${end2 - start2} ms`);/*102334155102334155
        递归所用时间:2476 ms高效的方法所用时间:0 ms*/


        从结果我们能很明显地看到,仅仅第40个值对于高效的方法来说根本不算什么,使用的时间几乎为0,而递归却因重复求值使用了2s以上的时间。因此可以想象,如果我们要获取斐波那契数列第1000个甚至第100000个的值,那递归求值得花多少时间啊?

        相关文章
        |
        2月前
        |
        测试技术
        【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
        【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
        |
        2月前
        剑指Offer LeetCode 面试题10- I. 斐波那契数列
        剑指Offer LeetCode 面试题10- I. 斐波那契数列
        29 0
        |
        存储
        剑指Offer - 面试题10:斐波那契数列
        剑指Offer - 面试题10:斐波那契数列
        66 0
        |
        机器学习/深度学习 算法 C++
        Interview:算法岗位面试—上海某公司算法岗位(偏机器学习,互联网金融行业)技术面试考点之数据结构相关考察点—斐波那契数列、八皇后问题、两种LCS问题
        Interview:算法岗位面试—上海某公司算法岗位(偏机器学习,互联网金融行业)技术面试考点之数据结构相关考察点—斐波那契数列、八皇后问题、两种LCS问题
        |
        算法
        面试:老师讲的递归解决斐波那契数列真的好吗
        在搞「模拟面试」的日子,我发现大家普遍有个问题就是,感觉自己的能力总是到了瓶颈期,写了好几年代码,感觉只是会的框架比以前多了而已。去大公司面试,屡战屡败,问失败原因,大多数人的答案都是,在三面数据结构与算法的时候,直接就挂了。
        1527 0
        |
        17天前
        |
        存储 算法 Java
        Java面试之SpringCloud篇
        Java面试之SpringCloud篇
        33 1
        |
        17天前
        |
        缓存 NoSQL Redis
        Java面试之redis篇
        Java面试之redis篇
        36 0
        |
        17天前
        |
        SQL 关系型数据库 MySQL
        java面试之MySQL数据库篇
        java面试之MySQL数据库篇
        23 0
        java面试之MySQL数据库篇
        |
        17天前
        |
        存储 缓存 前端开发
        Java八股文面试之多线程篇
        Java八股文面试之多线程篇
        24 0
        Java八股文面试之多线程篇