歡迎光臨
每天分享高質量文章

面試官問你斐波那契數列的時候不要高興得太早

前言

假如面試官讓你編寫求斐波那契數列的代碼時,是不是心中暗喜?不就是遞迴麽,早就會了。如果真這麼想,那就危險了。

遞迴解法

遞迴,在數學與計算機科學中,是指在函式的定義中使用函式自身的方法。
斐波那契數列的計算運算式很簡單:

F(n) = n; n = 0,1
F(n) = F(n-1) + F(n-2),n >= 2;

因此,我們能很快根據運算式寫出遞迴版的代碼:

/*fibo.c*/
#include 
#include 
/*求斐波那契數列遞迴版*/
unsigned long fibo(unsigned long int n)
{
    if(n <= 1)
        return n;
    else 
        return fibo(n-1) + fibo(n-2);
}
int main(int argc,char *argv[])
{
    if(1 >= argc)
    {
       printf("usage:./fibo num\n");
       return -1;
    }
    unsigned long  n = atoi(argv[1]);
    unsigned long  fiboNum = fibo(n);
    printf("the %lu result is %lu\n",n,fiboNum);
    return 0;
}

關鍵代碼只有4行。簡潔明瞭,一氣呵成。
編譯:

gcc -o fibo fibo.c

運行計算第5個斐波那契數:

$ time ./fibo 5
the 5 result is 5

real    0m0.001s
user    0m0.001s
sys    0m0.000s

看起來並沒有什麼不妥,運行時間也很短。
繼續計算第50個斐波那契數列:

$ time ./fibo 50
the 50 result is 12586269025

real    1m41.655s
user    1m41.524s
sys    0m0.076s

計算第50個斐波那契數的時候,竟然將近兩多鐘!

遞迴分析

為什麼計算第50個的時候竟然需要1分多鐘。我們仔細分析我們的遞迴演算法,就會發現問題,當我們計算fibo(5)的時候,是下麵這樣的:

                         |--F(1)
                  |
--F(2)|
           |
--F(3)|      |--F(0)
           |      |
    |--F(4)|      |--F(1)
    |
      |      
    |
      |      |--F(1)
    |      |--F(2)|
    |
             |--F(0)
F(5)|
             
    |             |--F(1)
    |      |--F(2)|
    |
      |      |--F(0)
    |--F(3)|
           |
           |
--F(1)

為了計算fibo(5),需要計算fibo(3),fibo(4);而為了計算fibo(4),需要計算fibo(2),fibo(3)……最終為了得到fibo(5)的結果,fibo(0)被計算了3次,fibo(1)被計算了5次,fibo(2)被計算了2次。可以看到,它的計算次數幾乎是指數級的!

因此,雖然遞迴演算法簡潔,但是在這個問題中,它的時間複雜度卻是難以接受的。除此之外,遞迴函式呼叫的越來越深,它們在不斷入棧卻遲遲不出棧,空間需求越來越大,雖然訪問速度高,但大小是有限的,最終可能導致棧上限溢位

在linux中,我們可以通過下麵的命令查看棧空間的軟限制:

$ ulimit -s
8192

可以看到,預設棧空間大小隻有8M。一般來說,8M的棧空間對於一般程式完全足夠。如果8M的棧空間不夠使用,那麼就需要重新審視你的代碼設計了。

遞迴改進版

既然我們知道最初版本的遞迴存在大量的重覆計算,那麼我們完全可以考慮將已經計算的值儲存起來,從而避免重覆計算,該版本代碼實現如下:

/*fibo0.c*/
#include 
#include 
/*求斐波那契數列,避免重覆計算版本*/
unsigned long fiboProcess(unsigned long *array,unsigned long n)
{
    if(n 2)
        return n;
    else
    {
        /*遞迴儲存值*/
        array[n] = fiboProcess(array,n-1) + array[n-2];
        return array[n];
    }
}

unsigned long  fibo(unsigned long  n)
{
    if(n <= 1)
        return n;
    unsigned long ret = 0;
    /*申請陣列用於儲存已經計算過的內容*/
    unsigned long *array = (unsigned long*)calloc(n+1,sizeof(unsigned long));
    if(NULL == array)
    {
        return -1;
    }
    array[1] = 1;
    ret = fiboProcess(array,n);
    free(array);
    array = NULL;
    return ret;
}
/**main函式部分與fibo.c相同,這裡省略*/

效率如何呢?

$ gcc -o fibo0 fibo0.c
$ time ./fibo0 50
the 50 result is 12586269025

real    0m0.002s
user    0m0.000s
sys    0m0.002s

可見其效率還是不錯的,時間複雜度為O(n)。但是特別註意的是,這種改進版的遞迴,雖然避免了重覆計算,但是呼叫鏈仍然比較長。

迭代解法

既然遞迴法不夠優雅,我們換一種方法。如果不用計算機計算,讓你去算第n個斐波那契數,你會怎麼做呢?我想最簡單直接的方法應該是:知道第一個和第二個後,計算第三個;知道第二個和第三個後,計算第四個,以此類推。最終可以得到我們需要的結果。這種思路,沒有冗餘的計算。基於這個思路,我們的C語言實現如下:

/*fibo1.c*/
#include 
#include 
/*求斐波那契數列迭代版*/
unsigned long  fibo(unsigned long  n)
{
    unsigned long  preVal = 1;
    unsigned long  prePreVal = 0;
    if(n <= 2)
        return n;
    unsigned long  loop = 1;
    unsigned long  returnVal = 0;
    while(loop     {
        returnVal = preVal +prePreVal;
        /*更新記錄結果*/
        prePreVal = preVal;
        preVal = returnVal;
        loop++;
    }
    return returnVal;
}
/**main函式部分與fibo.c相同,這裡省略*/

編譯並計算第50個斐波那契數:

$ gcc -o fibo1 fibo1.c
$ time ./fibo1 50
the 50 result is 12586269025

real    0m0.002s
user    0m0.000s
sys    0m0.002s

可以看到,計算第50個斐波那契數只需要0.002s!時間複雜度為O(n)。

尾遞迴解法

同樣的思路,但是採用尾遞迴的方法來計算。要計算第n個斐波那契數,我們可以先計算第一個,第二個,如果未達到n,則繼續遞迴計算,尾遞迴C語言實現如下:

/*fibo2.c*/
#include 
#include 
/*求斐波那契數列尾遞迴版*/
unsigned long fiboProcess(unsigned long n,unsigned long  prePreVal,unsigned long  preVal,unsigned long begin)
{
    /*如果已經計算到我們需要計算的,則傳回*/
    if(n == begin)
        return preVal+prePreVal;
    else
    {
        begin++;
        return fiboProcess(n,preVal,prePreVal+preVal,begin);
    }
}

unsigned long  fibo(unsigned long  n)
{
    if(n <= 1)
        return n;
    else 
        return fiboProcess(n,0,1,2);
}

/**main函式部分與fibo.c相同,這裡省略*/

效率如何呢?

$ gcc -o fibo2 fibo2.c
$ time ./fibo2 50
the 50 result is 12586269025

real    0m0.002s
user    0m0.001s
sys    0m0.002s

可見,其效率並不遜於迭代法。尾遞迴在函式傳回之前的最後一個操作仍然是遞迴呼叫。尾遞迴的好處是,進入下一個函式之前,已經獲得了當前函式的結果,因此不需要保留當前函式的環境,記憶體占用自然也是比最開始提到的遞迴要小。時間複雜度為O(n)。

矩陣快速冪解法

這是一種高效的解法,需要推導,對此不感興趣的可直接看最終推導結果。下麵的式子成立是顯而易見的,不多做解釋。

 

 

如果a為矩陣,等式同樣成立,後面我們會用到它。

假設有矩陣2*2矩陣A,滿足下麵的等式:

可以得到矩陣A:

因此也就可以得到下麵的矩陣等式:

再進行變換如下:

以此類推,得到:

實際上f(n)就是矩A^(n-1)中的A[0][0],或者是矩A^n中的A[0][1]。

那麼現在的問題就歸結為,如何求A^n,其中A為2*2的矩陣。根據我們最開始的公式,很容易就有思路,代碼實現如下:

/*fibo3.c*/
#include 
#include 
#include 
#define MAX_COL 2
#define MAX_ROW 2
typedef unsigned long MatrixType;
/*計算2*2矩陣乘法,這裡沒有寫成通用形式,有興趣的可以自己實現通用矩陣乘法*/
int matrixDot(MatrixType A[MAX_ROW][MAX_COL],MatrixType B[MAX_ROW][MAX_COL],MatrixType C[MAX_ROW][MAX_COL])
{
   /*C為傳回結果,由於A可能和C相同,因此使用臨時矩陣儲存*/
    MatrixType tempMa[MAX_ROW][MAX_COL] ;
    memset(tempMa,0,sizeof(tempMa));
    /*這裡簡便處理*/
    tempMa[0][0] = A[0][0* B[0][0] + A[0][1] * B [1][0];
    tempMa[0][1] = A[0][0* B[0][1] + A[0][1] * B [1][1];
    tempMa[1][0] = A[1][0* B[0][0] + A[1][1] * B [1][0];
    tempMa[1][1] = A[1][0* B[0][1] + A[1][1] * B [1][1];
    memcpy(C,tempMa,sizeof(tempMa));

    return 0;
}
MatrixType fibo(int n)
{
    if(n <= 1)
        return n;
    MatrixType result[][MAX_COL] = {1,0,0,1};
    MatrixType A[][2] = {1,1,1,0};
    while (n >
 0) 
    {
        /*判斷最後一位是否為1,即可知奇偶*/
        if (n&1) 
        {
            matrixDot(result,A,result);

        }
        n /= 2;
        matrixDot(A,A,A);
    }
    return result[0][1];
}
/**main函式部分與fibo.c相同,這裡省略*/

該演算法的關鍵部分在於對A^n的計算,它利用了我們開始提到的等式,對奇數和偶數分別處理。假設n為9,初始矩陣為INIT則計算過程如下:

  • 9為奇數,則計算INIT*A,隨後A變為A*A,n變為9/2,即為4

  • 4為偶數,則結果仍為INIT*A,隨後A變為,n變為4/2,即2

  • 2為偶數,則結果仍未INIT*A,隨後變A變為 ,n變為2/2,即1

  • 1為奇數,則結果為INIT*(A^8)*A

可以看到,計算次數類似與二分查找次數,其時間複雜度為O(logn)。
運行試試看:

$ gcc -o fibo3 fibo3.c
$ time ./fibo3 50
the 50 result is 12586269025

real    0m0.002s
user    0m0.002s
sys    0m0.000s

通項公式解法

斐波那契數列的通項公式為:

關於通項公式的求解,可以當成一道高考數列大題,有興趣的可以嘗試一下(提示:兩次構造等比數列)。C語言代碼實現如下:

/*fibo4.c*/
#include 
#include 
#include 
unsigned long fibo(unsigned long n)
{
    if(n <=1 )
        return n;
    return (unsigned long)((pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5));
}
/**main函式部分與fibo.c相同,這裡省略*/

來看一下效率:

$ gcc -o fibo4 fibo4.c -lm
$ time ./fibo4
the 50 result is 12586269025

real    0m0.002s
user    0m0.002s
sys    0m0.000s

計算第50個,速度還不錯。

串列法

如果需要求解的斐波那契數列的第n個在有限範圍內,那麼完全可以將已知的斐波那契數列儲存起來,在需要的時候讀取即可,時間複雜度可以為O(1)。

斐波那契數列應用

關於斐波那契數列在實際中很常見,數學上也有很多奇特的性質,有興趣的可在百科中查看。

總結

總結一下遞迴的優缺點:
優點:

  • 實現簡單

  • 可讀性好

缺點:

  • 遞迴呼叫,占用空間大

  • 遞迴太深,易發生棧上限溢位

  • 可能存在重覆計算

可以看到,對於求斐波那契數列的問題,使用一般的遞迴並不是一種很好的解法。
所以,當你使用遞迴方式實現一個功能之前,考慮一下使用遞迴帶來的好處是否抵得上它的代價。

【本文作者】

守望:一名好文學,好技術的開發者。在個人公眾號「編程珠璣」分享原創技術文章,期待一起交流學習

赞(0)

分享創造快樂