題目來源：?？途W(wǎng)-劍指Offer專題
題目地址：斐波那契數(shù)列

題目描述

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0）。n<=39

題目解析

方法一：
普通遞歸版求法，這種方法通常和漢諾塔一起被放在課本的遞歸教學(xué)部分，應(yīng)該是面試官不希望看到的算法。
$$F(n)=?\begin{array}{ll}0,& \text{n=0}\\ 1,& \text{n=1,2}\\ F(n?1)+F(n?2),& \text{n>2}\end{array}$$
利用上面遞推式，自頂向下進(jìn)行求解，因?yàn)?strong>存在大量的重疊子問題，時(shí)間復(fù)雜度為 $O(2^n)$。

public class Solution {public int Fibonacci(int n) {if (n == 0) return 0;if (n == 1) return 1;return Fibonacci(n - 1) + Fibonacci(n - 2);} }

方法二：
我們可以將遞推式的求解從自頂向下改為自底向上（循環(huán)實(shí)現(xiàn)）。簡(jiǎn)而言之，我們已知前兩項(xiàng)的值，然后我們就可以用前兩項(xiàng)的值求出第3項(xiàng)的值，接著求第4、第5、……，直到求出第n項(xiàng)的值。（廢話）

實(shí)現(xiàn)過程如下圖所示，兩個(gè)相同顏色的箭頭可以確定一個(gè)新的數(shù)列項(xiàng)。

上述算法的時(shí)間復(fù)雜度為 $O(n)$，在面試中夠用了，如果還是覺得簡(jiǎn)單可以繼續(xù)往下看。

public class Solution {public int Fibonacci(int n) {if (n == 0) {return 0;}int a = 1, b = 1;for (int i = 1; i <= n - 2; i++) {a = a + b;b = a - b;}return a;} }

方法三：
我們知道：
$$\begin{gathered} F(n)=F(n?1)+F(n?2) \\ F(n?1)=F(n?1)+0?F(n?2) \end{gathered}$$
將其轉(zhuǎn)化成矩陣運(yùn)算可得

$$\left(\begin{array}{c}F(n)\\ F(n?1)\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)?\left(\begin{array}{c}F(n?1)\\ F(n?2)\end{array}\right)$$
而右邊的$2\times 1$階矩陣又可以進(jìn)一步分解為
$$\left(\begin{array}{c}F(n?1)\\ F(n?2)\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)?\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)?\left(\begin{array}{c}F(n?2)\\ F(n?3)\end{array}\right)$$
按照這樣一直分解下去直到右邊的$2\times 1$階矩陣F(2),F(1),即
$$\left(\begin{array}{c}F(n)\\ F(n?1)\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^{n?2}?\left(\begin{array}{c}F(2)\\ F(1)\end{array}\right)$$
這時(shí)利用矩陣版的快速冪求解其中的矩陣冪乘，就可以在 $O(logn)$ 的時(shí)間復(fù)雜度下得出Fibonacci數(shù)列的第n項(xiàng)的值。

這種方法通常是用在算法比賽中，在面試中容易裝逼失敗不適合使用，這里也不掛板子了。

方法四：
根據(jù)上面的遞推式，利用我們高中學(xué)過的“待定系數(shù)法”可以推導(dǎo)出斐波那契數(shù)列的通項(xiàng)公式。公式如下，（推導(dǎo)過程略）
$$F(n)=\frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2}{)}^n?(\frac{1?\sqrt{5}}{2}{)}^n]$$
公式法時(shí)間復(fù)雜度為 $O(1)$ ? 感覺不然，求公式中的 $n$ 次方應(yīng)該要用上快速冪，我個(gè)人認(rèn)為時(shí)間復(fù)雜度應(yīng)該也是 $O(logn)$。（我要滾去看源碼了 ）

public class Solution {public int Fibonacci(int n) {double a = Math.sqrt(5)/5;double b = Math.pow((1+ Math.sqrt(5))/2, n);double c = Math.pow((1- Math.sqrt(5))/2, n);return (int)(a * (b - c));} }

后記:
如果你在寫出循環(huán)版之后，再給面試官描述后面兩種算法，并流暢寫出通項(xiàng)公式的推導(dǎo)過程，相信肯定可以取得面試官的芳心~

---

如果本文對(duì)你有所幫助，要記得點(diǎn)贊哦~

總結(jié)

以上是生活随笔為你收集整理的剑指Offer #07 斐波那契数列（四种解法）| 图文详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。