斐波那契数列的三种解法

写一个函数,输入n,求斐波那契数列的第n项。 斐波那契数列的定义如下  

一、效率极低的解法(递归)

课本的上为了讲解递归算法,经常用这个例子。让我们看一下它的实现
  1. package algorithm;
  2. public class Fibonacci_recursion {
  3.     // 1 1 2 3 5 8 13 21 34 55
  4.     long Fibonacci(int n) {
  5.         if(n<=0return 0;
  6.         if(n==1return 1;
  7.         if(n==2return 1;
  8.         if(n>2return Fibonacci(n-1)+Fibonacci(n-2);
  9.         return 0;
  10.     }
  11.     public static void main(String args[]) {
  12.         Fibonacci_recursion f = new Fibonacci_recursion();
  13.         long startTime = System.currentTimeMillis();
  14.         long x = f.Fibonacci(40);
  15.         long endTime = System.currentTimeMillis();
  16.         System.out.println("程序运行时间:"+(endTime-startTime)+"ms");//534
  17.         System.out.println(x);
  18.     }
  19. }
因为随着 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)。 代码实现
  1. package algorithm;
  2. public class Fibonacci_linear {
  3.     // 1 1 2 3 5 8 13 21 34 55
  4.     long Fibonacci(int n) {
  5.         long num1 = 0, num2=1, temp=0;
  6.         for(int i=1;i<n;i++) {
  7.             temp = num1+num2;
  8.             num1 = num2;
  9.             num2 = temp;
  10.         }
  11.         return num2;
  12.     }
  13.     public static void main(String args[]) {
  14.         Fibonacci_linear f = new Fibonacci_linear();
  15.         long startTime = System.currentTimeMillis();
  16.         long x = f.Fibonacci(4000000);
  17.         long endTime = System.currentTimeMillis();
  18.         System.out.println("程序运行时间:"+(endTime-startTime)+"ms");//0
  19.         System.out.println(x);
  20.     }
  21. }
由于时间复杂度为 O(n) ,也就是说,随着 n 的变大我们的时间都是可以忽略的,无论是 Fibonacci(40) ,Fibonacci(400) ,Fibonacci(4000),Fibonacci(4000000) 都是可以计算且时间都很短的。 比如求 Fibonacci(4000000) 最终结果如下 程序运行时间:5ms 6558868233897966651 可见该方法比第一种的递归好多少,这也应该是面试官所青睐的。  

三、时间复杂度 O(logn) 但不实用的算法

待补充...    

发表评论

目前评论:1