[算法]還在用遞歸實現斐波那契數列，面試官一定會鄙視你到死
- 2019 年 10 月 20 日
- 筆記
斐波那契數列指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……
我記得在初學C語言的時候，大學老師經常會講一些常見的數學問題及遞歸的使用，其中斐波那契數列就是一定會被拿出來舉例的。在後來工作中，面試做面試題的時候，也很大概率會出現編寫算法實現斐波那契額數列求值。可以說，在我們編程道路上，編寫算法實現斐波那契數列是每個程序員必定會做的一件事。昨天去參加騰訊課堂舉辦的一個線下活動，活動中有一位嘉賓，是某課堂的創始人，也是算法課程的講師，就講到了這個問題，算是顛覆了我對該問題的認知。本文就根據這名講師的講解，來分析和整理一下該問題算法的實現。
下面，我們來看看其中幾種常見的算法，並分析其效率。
1、遞歸法
通過觀察，我們會發現其中的規律，第一項和第二項的值均為1，後面每項的值都是前兩項值之和，所以我們很多人基本上都會使用遞歸來實現，常見的算法如下：
1 public int fib(int n) { 2 if (n == 1 || n == 2) { 3 return 1; 4 } 5 return fib(n - 2) + fib(n - 1); 6 }
這段代碼看起來非常的簡潔和優雅，我想我們絕大多數的人平時也都是這麼寫的吧，在此之前筆者就一直都是這麼寫的，而且在我的知識儲備中也就只知道有這樣一種算法。
實際上，當n還比較小的時候，用遞歸法來實現是沒有什麼問題的，但是當n稍微大一點的時候，比如n=45的時候，我們通過如下測試代碼來看看它的執行結果：
1 MyClass myClass = new MyClass(); 2 long t1 = System.currentTimeMillis(); 3 int n = 45; 4 int result = myClass.fib(n); 5 long t2 = System.currentTimeMillis(); 6 System.out.println("n=" + n + ";result=" + result + ";time=" + (t2 - t1));
得到結果為：
n=45;result=1134903170;time=2881
我們發現執行這段代碼，花費的時間是2881ms。如果值再大一點，如n=48：
n=48;result=512559680;time=11746
時間達到了11s以上了！如果n再稍微大一點，所消耗的時間是成指數級增長的，比如n=64的時候，所消耗的時間可能是兩三百年！不信的話，讀者可以試試！
這樣看來，就非常可怕了，我們一直認為毫無問題的看起來既簡潔又優雅的算法，居然是這麼耗時的，這簡直就是一段垃圾代碼。
我們用一張圖來簡單分析一下該算法的執行過程，以n=6為例：
我們會發現f(n)這個方法被調用了很多次，而且其中重複率非常之高，也就是說被重複計算了很多次，如果n稍微大一點這棵樹會非常龐大。這裡我們可以看出，每個節點就需要計算一次，總計算的次數就是該二叉樹節點的數量，可見其時間複雜度為O(2n)，是指數級的，其空間複雜度也就是該二叉樹的高度，為O(n)。這樣來看，我們應該就清楚了，為什麼這段代碼效率如此低下了吧。
2、數組保存法（該名稱是自己命名的，想不出什麼好名字了，不喜勿噴哈…）
為了避免無數次重複，可以從n=1開始往上計算，並把每一個計算出來的數據，用一個數組保存，需要最終值時直接從數組中取即可，算法如下：
1 public int fib(int n) { 2 int[] fib = new int[n]; 3 fib[0] = 1; 4 fib[1] = 1; 5 for (int i = 2; i < n; i++) { 6 fib[i] = fib[i - 2] + fib[i - 1]; 7 } 8 return fib[n - 1]; 9 }
我們也分別取n=45和n=48來看看執行結果
n=45;result=1134903170;time=0
n=48;result=512559680;time=0
消耗的時間都是0（我這裡獲取的時間是精確到ms級別的，前後的時間差在1ms以下，所以這裡計算出來的結果為0，實際耗時不可能為0，後續不贅述），可見執行效率提高了很多。這種算法主要有一個for循環，其時間複雜度為O(n)，期間需要開闢一個長度為n的數組，所以空間複雜度也為O(n)，這就在上述算法的基礎上極大地提升了效率。
3、滾動數組法（這個命名是讀者評論區提出來的，雖然不是很理解，不過還是採納吧，總比我自己瞎命名好，感謝這位童鞋）
儘管上述算法已經很高效了，但我們還是會發現一個問題，其實整個數組中，每次計算時都只需要最新的3個值，前面的值計算完後就不再需要了。比如，計算到第10次時，需要的數組空間只有第8和第9兩個空間，前面第1到第7個空間其實就不再需要了。所以我們還可以改進，通過3個變量來存儲數據，算法如下：
1 public int fib(int n) { 2 int first = 1; 3 int second = 1; 4 int third = 2; 5 for (int i = 3; i <= n; i++) { 6 third = first + second; 7 first = second; 8 second = third; 9 } 10 return third; 11 }
時間複雜度仍然為O(n)，而空間複雜度為常量級別3，即空間複雜度為0，所以這種方法是非常高效的。
4、公式法
實際上，求斐波那契數列值有一個公式：
可以通過該公式來實現算法：
1 public int fib(int n) { 2 double c = Math.sqrt(5); 3 return (int) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c); 4 }
其時間複雜度和空間複雜度就取決於JDK中這些數學公式的實現了，執行效率也是非常高的：
n=48;result=512559680;time=0
5、尾遞歸法
這裡先亮出該算法吧：
1 public int fib5(int n, int first, int second) { 2 if (n <= 1) { 3 return first; 4 } else { 5 return fib5(n-1,second,first+second); 6 } 7 }
其實我起初覺得這種方法的實現和第三種算法的中心思想挺類似的，雖然乍一看好像差別挺大，但仔細分析，也都是通過兩個變量保存計算值，傳遞給下一次進行計算，遞歸的過程中也是根據n值變化逐步重複運算，和循環差不多，時間複雜度和空間複雜度也都一樣，所以最初就沒有單獨列出來。後來評論區有童鞋提出來了，仔細想想，這種方式從形式上和第三種算法差別還是挺大的，而且簡潔很多，優雅很多，也有一個響亮的名字，還是單獨列出來更好，這裡也感謝評論區童鞋們的寶貴意見。
由於筆者水平有限，文章中一定有很多需要改進的地方，如果讀者發現本文有描述不正確或者不妥的地方，請不吝賜教，非常感謝！
