《劍指Offer》計算斐波那契數列的第n項

斐波那契數列的定義為：

f ( n ) = { 0 , if  n  = 0 1 , if  n  = 1 f ( n − 1 ) + f ( n − 2 ) if  n  > 1 f(n) = \begin{cases} 0, & \text{if $n$ = 0} \\ 1, & \text{if $n$ = 1}\\ f(n-1) + f(n-2) & \text{if $n$ > 1} \end{cases} f(n)=⎩⎪⎨⎪⎧​0,1,f(n−1)+f(n−2)​if n = 0if n = 1if n > 1​

計算斐波那契數列的第n項有三種方法。

遞歸法

考慮到斐波那契數列的定義，我們很容易寫出下面的代碼：

int f(int n)
{
	if(n <= 0)
		return 0;
	if(n == 1)
		return 1;
	return f(n-1) + f(n-2);
}
           

考慮一下這種方法的時間複雜度，容易寫出遞歸式：

T ( n ) = { 1 if  n  = 0 1 if  n  = 1 T ( n − 1 ) + T ( n − 2 ) + 1 if  n  > 1 T(n) = \begin{cases} 1 & \text{if $n$ = 0} \\ 1 & \text{if $n$ = 1}\\ T(n-1) + T(n-2) + 1& \text{if $n$ > 1} \end{cases} T(n)=⎩⎪⎨⎪⎧​11T(n−1)+T(n−2)+1​if n = 0if n = 1if n > 1​

可以看到 T ( n ) T(n) T(n)的增長速度是比斐波那契數列更快的，而斐波那契數列就是以指數形式增長的，是以 T ( n ) T(n) T(n)至少也是指數增長的。

顯然，一種指數複雜度的算法是難以滿足要求的。

正常解法

遞歸法之是以複雜度這麼高的原因是，對于同一個值，進行了反複計算。是以我們采用一種方法，用一個數組記錄所有計算過的值，這樣就避免了重複計算。

代碼如下

int Fibonacci(int n) {
        int a[n+1];
        a[0] = 0;
        a[1] = 1;
        for(int i=0; i<n-1; i++)
        {
            a[i+2] = a[i+1] + a[i];
        }
        return a[n];
    }
           

顯然這種方法的時間複雜度是 O ( n ) O(n) O(n)

矩陣幂法

這種方法基于一個數學公式:

[ f ( n ) f ( n − 1 ) f ( n − 2 ) f ( n − 2 ) ] = [ 1 1 1 0 ] n − 1 \begin{bmatrix} f(n) & f(n-1) \\ f(n-2) & f(n-2) \\ \end{bmatrix} = \begin{bmatrix} 1& 1 \\ 1 & 0 \\ \end{bmatrix} ^{n-1} [f(n)f(n−2)​f(n−1)f(n−2)​]=[11​10​]n−1

我們知道求矩陣幂的時間複雜度是 O ( l o g n ) O(logn) O(logn)，是以這種方法求解斐波那契數列第n項的時間複雜度也是 O ( l o g n ) O(logn) O(logn)。