斐波那契数列的算法的优雅实现

斐波那契数列简称兔子数列,是一道非常高频的面试题。

为什么它如此受面试官们的欢迎?原因有三:

第一:这个题目的答案简单;

第二:区分度高,水平不同,写出的代码必然不同;

第三:这个题目的变种很多,比如说“上一个N台阶的楼梯,每次只能走一格或者二格,总共有多少种走法?“,不小心就能绕进去,但是归根结底就是一堆兔子怎么生;

斐波那契数列是什么?每一项都等于它前两项和的数列。

第一种解法:传统递归,性能在N>40的时候急剧下降。代码如下:

解法1 递归

第二种解法:迭代(动态规划思想)。不难看出该算法的时间复杂度是O(n) 。代码如下:

解法2 迭代

第三种解法:从数学公式的角度,利用特征方程、母函数来求解。时间复杂度是O(log(n))。代码如下:

解法3 组合数学公式
Math.pow函数的实现代码

自己实现Pow函数的思路,把要求解n次幂的n转换成二进制的形式,凡是二进制有1的位,都乘以对应次数的x的倍数,每次循环的时候处理n的二进制的一位,从最小的一位开始,看它最后一位如果能被2整除,就可以为它乘以对应x的倍数,0不做处理,最后去除最后一位,自此循环看最后一位是0还是1,重复上面的步骤。这样就能在x的n次方内求出,进而得出时间复杂度是log(n)。但是受系统的浮点数(操作系统的浮点运算相当耗时)的影响,切记加上一次Math.round进行取整操作。

第四种解法:矩阵的幂运算。

先来简单回顾一下线性代数的知识,方便理解解法幂运算。

矩阵乘法
矩阵乘法与矩阵的幂
解法4 矩阵运算

今天的学习结束,俗话说的好:“每天进步一点点,未来进步一大截!”

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。