最近去滴滴面试的一道题:斐波拉契数列非递归实现

斐波拉契数列这里复习一下:

0,1,1,2,3,5,8,13 ......

数列很简单,就是当前的项的值 等于 紧靠着的前面两项值的和, 立马想出来用递归几行代码就可以实现:

 1 /**
 2      * n是自然数
 3      * 递归实现
 4      * @param n
 5      * @return
 6      */
 7     public int fibonacci(int n) {
 8         if (n == 0)
 9             return 0;
10         if (n == 1 || n == 2)
11             return 1;
12         return fibonacci(n - 2) + fibonacci(n - 1);
13     }

由于递归循环调用方法,占用栈空间,n = 50 时,运行上面的代码,结果已经出不来了,

这里从上面的代码推出非递归实现:

 1 /**
 2      * n是自然数
 3      * 非递归实现
 4      *
 5      * @param n
 6      * @return
 7      */
 8     public int fibonacci(int n) {
 9         if (n == 0)
10             return 0;
11         if (n == 1 || n == 2)
12             return 1;
13         int a, b;
14         int sum = 0;
15         a = b = 1;
16         //这里从2开始遍历
17         for (int i = 2; i < n; i++) {
18             sum = a + b;
19             a = b;
20             b = sum;
21         }
22         return sum;
23     }

再次运行,结果很快就出来了

 结果倒是出来了,可是这样解的结果,时间复杂度是 O(N),有没有更快的解法呢,答案就是特征方程,求通向公式

拿出了数学书,重新复习了一下数列知识,推到了一下通向公式,过程如下:

由最终的结果可以看出这个问题最终转换成了求幂操作, 而求幂又可以用分治法的方式,使得最终的时间复杂度变成 O(Log2N)

 1       /**
 2      * 
 3      * @param base 底数
 4      * @param exponent 幂
 5      * @return
 6      */
 7     private double power(double base, int exponent) {
 8         if(exponent == 0)
 9             return 1;
10         if(exponent == 1)
11             return base;
12         double result = power(base, exponent >> 1);
13         result *= result;
14         if((exponent & 1) == 1)
15             result *= base;
16         return result;
17     }    
原文地址:https://www.cnblogs.com/blentle/p/8434432.html