斐波那契数列的三种解法

写一个函数,输入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) 但不实用的算法

待补充...

 

 

  • 微信
  • 赶快加我聊天吧
  • weinxin
  • 博客交流群
  • 海纳百川,大家来水
  • weinxin
言曌

发表评论

:?::razz::sad::evil::!::smile::oops::grin::eek::shock::???::cool::lol::mad::twisted::roll::wink::idea::arrow::neutral::cry::mrgreen: