斐波那契数列的三种解法

avatar 2017年10月11日09:10:19 5 3933 views
博主分享免费Java教学视频，B站账号：Java刘哥
写一个函数，输入n，求斐波那契数列的第n项。 斐波那契数列的定义如下  

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

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

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

待补充...    
历史上的今天
十月
11日
  • 微信
  • 交流学习，有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享，问题解决，技术交流。群号：590480292
  • weinxin
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0