斐波那契数列的三种解法

言曌 2017年10月11日09:10:19 5 4750 views

博主分享免费Java教学视频，B站账号：Java刘哥，长期提供技术问题解决、项目定制：本站商品点此

写一个函数，输入n，求斐波那契数列的第n项。

斐波那契数列的定义如下

一、效率极低的解法（递归）

课本的上为了讲解递归算法，经常用这个例子。让我们看一下它的实现

package algorithm;
public class Fibonacci_recursion {
// 1 1 2 3 5 8 13 21 34 55
long Fibonacci(int n) {
if(n<=0) return 0;
if(n==1) return 1;
if(n==2) return 1;
if(n>2) return Fibonacci(n-1)+Fibonacci(n-2);
return 0;
}
public static void main(String args[]) {
Fibonacci_recursion f = new Fibonacci_recursion();
long startTime = System.currentTimeMillis();
long x = f.Fibonacci(40);
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间："+(endTime-startTime)+"ms");//534
System.out.println(x);
}
}

因为随着 n 的大小变化，返回值会越来越大，防止越界，这里使用 long 而不是 int 类型。

我们知道，递归算法的执行时间是随着 n 的大小变化而成指数递增。

博主在自己的机器上测试。求 4 的斐波那契项，用时可能可以忽略, 0 ms；求 40 的斐波那契项用时 534 ms; 然后求 50 呢，机器的风扇开始响了，几十秒过去了，都没结果。

可见，使用递归求斐波那契数列项，容易理解，但是效率真的很 bad 。

因为，当我们求 Fibonacci(10) 的时候，要求 Fibonacci(9) 和 Fibonacci(8); 同样，求 Fibonacci(9) 的时候要先求 Fibonacci(8) 和 Fibonacci(7)... 这下面会有很多重复计算的过程。比如几乎计算所有的项都算了 Fibonacci(1)+Fibonacci(2)。

如果我们把这个用树形结构来表示，可以看做一个根节点在上的自上而下的二叉树，每次计算都会重复计算很多子节点。

二、线性解法，时间复杂度 O(n)

如果我们不使用递归算法，而是使用常规的解法，效果是不是会高很多呢？至少要把时间复杂度给降下来吧。

常规解法怎么做呢？

如果是求 Fibonacci(10)，我们先把求 Fibonacci(1), Fibonacci(2)，然后根据前两者求 Fibonacci(3)，然后再求 Fibonacci(4)，一直求到 Fibonacci(10) 。

这其实只需要一个 for 循环，所有，时间复杂度为 O(n)。

代码实现

package algorithm;
public class Fibonacci_linear {
// 1 1 2 3 5 8 13 21 34 55
long Fibonacci(int n) {
long num1 = 0, num2=1, temp=0;
for(int i=1;i<n;i++) {
temp = num1+num2;
num1 = num2;
num2 = temp;
}
return num2;
}
public static void main(String args[]) {
Fibonacci_linear f = new Fibonacci_linear();
long startTime = System.currentTimeMillis();
long x = f.Fibonacci(4000000);
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间："+(endTime-startTime)+"ms");//0
System.out.println(x);
}
}

由于时间复杂度为 O(n) ，也就是说，随着 n 的变大我们的时间都是可以忽略的，无论是 Fibonacci(40) ,Fibonacci(400) ,Fibonacci(4000)，Fibonacci(4000000) 都是可以计算且时间都很短的。

比如求 Fibonacci(4000000) 最终结果如下

程序运行时间：5ms

6558868233897966651

可见该方法比第一种的递归好多少，这也应该是面试官所青睐的。