日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
可能對遞歸理解的還不夠！還差得遠！

上周小結(jié)的時候就提到了，在「算法匯總」里算法性能分析這塊還沒補全，后序會補上，所以這就來了，要分析遞歸的性能咱就分析個清清楚楚!

之前在通過一道面試題目，講一講遞歸算法的時間復(fù)雜度!中詳細講解了遞歸算法的時間復(fù)雜度，但沒有講空間復(fù)雜度。

本篇講通過求斐波那契數(shù)列和二分法再來深入分析一波遞歸算法的時間和空間復(fù)雜度，細心看完，會刷新對遞歸的認知!

遞歸求斐波那契數(shù)列的性能分析

先來看一下求斐波那契數(shù)的遞歸寫法。

 
 
 
 
    
  
  
  
  
  1. int fibonacci(int i) { 
    2.   
  
  
  
  2.        if(i <= 0) return 0; 
    3.   
  
  
  
  3.        if(i == 1) return 1; 
    4.   
  
  
  
  4.        return fibonacci(i-1) + fibonacci(i-2); 
    5.   
  
  
  
  5. } 
    6.

對于遞歸算法來說，代碼一般都比較簡短，從算法邏輯上看，所用的存儲空間也非常少，但運行時需要內(nèi)存可不見得會少。

時間復(fù)雜度分析

來看看這個求斐波那契的遞歸算法的時間復(fù)雜度是多少呢?

在講解遞歸時間復(fù)雜度的時候，我們提到了遞歸算法的時間復(fù)雜度本質(zhì)上是要看: 遞歸的次數(shù) * 每次遞歸的時間復(fù)雜度。

可以看出上面的代碼每次遞歸都是O(1)的操作。再來看遞歸了多少次，這里將i為5作為輸入的遞歸過程 抽象成一顆遞歸樹，如圖：

從圖中，可以看出f(5)是由f(4)和f(3)相加而來，那么f(4)是由f(3)和f(2)相加而來 以此類推。

在這顆二叉樹中每一個節(jié)點都是一次遞歸，那么這棵樹有多少個節(jié)點呢?

我們之前也有說到，一棵深度(按根節(jié)點深度為1)為k的二叉樹最多可以有 2^k - 1 個節(jié)點。

所以該遞歸算法的時間復(fù)雜度為 O(2^n) ，這個復(fù)雜度是非常大的，隨著n的增大，耗時是指數(shù)上升的。

來做一個實驗，大家可以有一個直觀的感受。

以下為C++代碼，來測一下，讓我們輸入n的時候，這段遞歸求斐波那契代碼的耗時。

 
 
 
 
    
  
  
  
  
  1. #include  
    2.   
  
  
  
  2. #include  
    3.   
  
  
  
  3. #include  
    4.   
  
  
  
  4. using namespace std; 
    5.   
  
  
  
  5. using namespace chrono; 
    6.   
  
  
  
  6. int fibonacci(int i) { 
    7.   
  
  
  
  7.        if(i <= 0) return 0; 
    8.   
  
  
  
  8.        if(i == 1) return 1; 
    9.   
  
  
  
  9.        return fibonacci(i - 1) + fibonacci(i - 2); 
    10.   
  
  
  
  10. } 
    11.   
  
  
  
  11. void time_consumption() { 
    12.   
  
  
  
  12.     int n; 
    13.   
  
  
  
  13.     while (cin >> n) { 
    14.   
  
  
  
  14.         milliseconds start_time = duration_cast( 
    15.   
  
  
  
  15.             system_clock::now().time_since_epoch() 
    16.   
  
  
  
  16.         ); 
    17.   
  
  
  
  17.  
    18.   
  
  
  
  18.         fibonacci(n); 
    19.   
  
  
  
  19.  
    20.   
  
  
  
  20.         milliseconds end_time = duration_cast( 
    21.   
  
  
  
  21.             system_clock::now().time_since_epoch() 
    22.   
  
  
  
  22.         ); 
    23.   
  
  
  
  23.         cout << milliseconds(end_time).count() - milliseconds(start_time).count() 
    24.   
  
  
  
  24.             <<" ms"<< endl; 
    25.   
  
  
  
  25.     } 
    26.   
  
  
  
  26. } 
    27.   
  
  
  
  27. int main() 
    28.   
  
  
  
  28. { 
    29.   
  
  
  
  29.     time_consumption(); 
    30.   
  
  
  
  30.     return 0; 
    31.   
  
  
  
  31. } 
    32.

根據(jù)以上代碼，給出幾組實驗數(shù)據(jù)：

測試電腦以2015版MacPro為例，CPU配置：2.7 GHz Dual-Core Intel Core i5

測試數(shù)據(jù)如下：

  • n = 40，耗時：837 ms
  • n = 50，耗時：110306 ms

可以看出，O(2^n)這種指數(shù)級別的復(fù)雜度是非常大的。

所以這種求斐波那契數(shù)的算法看似簡潔，其實時間復(fù)雜度非常高，一般不推薦這樣來實現(xiàn)斐波那契。

其實罪魁禍首就是這里的兩次遞歸，導(dǎo)致了時間復(fù)雜度以指數(shù)上升。

 
 
 
 
    
  
  
  
  
  1. return fibonacci(i-1) + fibonacci(i-2); 
    2.

可不可以優(yōu)化一下這個遞歸算法呢。主要是減少遞歸的調(diào)用次數(shù)。

來看一下如下代碼：

 
 
 
 
    
  
  
  
  
  1. // 版本二 
    2.   
  
  
  
  2. int fibonacci(int first, int second, int n) { 
    3.   
  
  
  
  3.     if (n <= 0) { 
    4.   
  
  
  
  4.         return 0; 
    5.   
  
  
  
  5.     } 
    6.   
  
  
  
  6.     if (n < 3) { 
    7.   
  
  
  
  7.         return 1; 
    8.   
  
  
  
  8.     } 
    9.   
  
  
  
  9.     else if (n == 3) { 
    10.   
  
  
  
  10.         return first + second; 
    11.   
  
  
  
  11.     } 
    12.   
  
  
  
  12.     else { 
    13.   
  
  
  
  13.         return fibonacci(second, first + second, n - 1); 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15. } 
    16.

這里相當于用first和second來記錄當前相加的兩個數(shù)值，此時就不用兩次遞歸了。

因為每次遞歸的時候n減1，即只是遞歸了n次，所以時間復(fù)雜度是 O(n)。

同理遞歸的深度依然是n，每次遞歸所需的空間也是常數(shù)，所以空間復(fù)雜度依然是O(n)。

代碼(版本二)的復(fù)雜度如下：

  • 時間復(fù)雜度：O(n)
  • 空間復(fù)雜度：O(n)

此時再來測一下耗時情況驗證一下：

 
 
 
 
    
  
  
  
  
  1. #include  
    2.   
  
  
  
  2. #include  
    3.   
  
  
  
  3. #include  
    4.   
  
  
  
  4. using namespace std; 
    5.   
  
  
  
  5. using namespace chrono; 
    6.   
  
  
  
  6. int fibonacci_3(int first, int second, int n) { 
    7.   
  
  
  
  7.     if (n <= 0) { 
    8.   
  
  
  
  8.         return 0; 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10.     if (n < 3) { 
    11.   
  
  
  
  11.         return 1; 
    12.   
  
  
  
  12.     } 
    13.   
  
  
  
  13.     else if (n == 3) { 
    14.   
  
  
  
  14.         return first + second; 
    15.   
  
  
  
  15.     } 
    16.   
  
  
  
  16.     else { 
    17.   
  
  
  
  17.         return fibonacci_3(second, first + second, n - 1); 
    18.   
  
  
  
  18.     } 
    19.   
  
  
  
  19. } 
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21. void time_consumption() { 
    22.   
  
  
  
  22.     int n; 
    23.   
  
  
  
  23.     while (cin >> n) { 
    24.   
  
  
  
  24.         milliseconds start_time = duration_cast( 
    25.   
  
  
  
  25.             system_clock::now().time_since_epoch() 
    26.   
  
  
  
  26.         ); 
    27.   
  
  
  
  27.  
    28.   
  
  
  
  28.         fibonacci_3(0, 1, n); 
    29.   
  
  
  
  29.  
    30.   
  
  
  
  30.         milliseconds end_time = duration_cast( 
    31.   
  
  
  
  31.             system_clock::now().time_since_epoch() 
    32.   
  
  
  
  32.         ); 
    33.   
  
  
  
  33.         cout << milliseconds(end_time).count() - milliseconds(start_time).count() 
    34.   
  
  
  
  34.             <<" ms"<< endl; 
    35.   
  
  
  
  35.     } 
    36.   
  
  
  
  36. } 
    37.   
  
  
  
  37. int main() 
    38.   
  
  
  
  38. { 
    39.   
  
  
  
  39.     time_consumption(); 
    40.   
  
  
  
  40.     return 0; 
    41.   
  
  
  
  41. } 
    42.

測試數(shù)據(jù)如下：

  • n = 40，耗時：0 ms
  • n = 50，耗時：0 ms

大家此時應(yīng)該可以看出差距了!!

空間復(fù)雜度分析

說完了這段遞歸代碼的時間復(fù)雜度，再看看如何求其空間復(fù)雜度呢，這里給大家提供一個公式：遞歸算法的空間復(fù)雜度 = 每次遞歸的空間復(fù)雜度 * 遞歸深度

為什么要求遞歸的深度呢?

因為每次遞歸所需的空間都被壓到調(diào)用棧里(這是內(nèi)存管理里面的數(shù)據(jù)結(jié)構(gòu)，和算法里的棧原理是一樣的)，一次遞歸結(jié)束，這個棧就是就是把本次遞歸的數(shù)據(jù)彈出去。所以這個棧最大的長度就是遞歸的深度。

此時可以分析這段遞歸的空間復(fù)雜度，從代碼中可以看出每次遞歸所需要的空間大小都是一樣的，所以每次遞歸中需要的空間是一個常量，并不會隨著n的變化而變化，每次遞歸的空間復(fù)雜度就是O(1)。

在看遞歸的深度是多少呢?如圖所示：

遞歸第n個斐波那契數(shù)的話，遞歸調(diào)用棧的深度就是n。

那么每次遞歸的空間復(fù)雜度是O(1)， 調(diào)用棧深度為n，所以這段遞歸代碼的空間復(fù)雜度就是O(n)。

 
 
 
 
    
  
  
  
  
  1. int fibonacci(int i) { 
    2.   
  
  
  
  2.        if(i <= 0) return 0; 
    3.   
  
  
  
  3.        if(i == 1) return 1; 
    4.   
  
  
  
  4.        return fibonacci(i-1) + fibonacci(i-2); 
    5.   
  
  
  
  5. } 
    6.

最后對各種求斐波那契數(shù)列方法的性能做一下分析，如題：

可以看出，求斐波那契數(shù)的時候，使用遞歸算法并不一定是在性能上是最優(yōu)的，但遞歸確實簡化的代碼層面的復(fù)雜度。

二分法(遞歸實現(xiàn))的性能分析

帶大家再分析一段二分查找的遞歸實現(xiàn)。

 
 
 
 
    
  
  
  
  
  1. int binary_search( int arr[], int l, int r, int x) { 
    2.   
  
  
  
  2.     if (r >= l) { 
    3.   
  
  
  
  3.         int mid = l + (r - l) / 2; 
    4.   
  
  
  
  4.         if (arr[mid] == x) 
    5.   
  
  
  
  5.             return mid; 
    6.   
  
  
  
  6.         if (arr[mid] > x) 
    7.   
  
  
  
  7.             return binary_search(arr, l, mid - 1, x); 
    8.   
  
  
  
  8.         return binary_search(arr, mid + 1, r, x); 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10.     return -1; 
    11.   
  
  
  
  11. } 
    12.

都知道二分查找的時間復(fù)雜度是O(logn)，那么遞歸二分查找的空間復(fù)雜度是多少呢?

我們依然看 每次遞歸的空間復(fù)雜度和遞歸的深度

首先我們先明確這里的空間復(fù)雜度里面的n是什么?二分查找的時候n就是指查找數(shù)組的長度，也就是代碼中的arr數(shù)組。

每次遞歸的空間復(fù)雜度可以看出主要就是參數(shù)里傳入的這個arr數(shù)組，即：O(n)。

再來看遞歸的深度，二分查找的遞歸深度是logn ，遞歸深度就是調(diào)用棧的長度，那么這段代碼的空間復(fù)雜度為 n * logn = O(nlogn)。

有同學(xué)問了：為什么網(wǎng)上很多人說遞歸二分查找的空間復(fù)雜度是O(logn)，而不是O(nlogn)呢?

其實還是因為這個數(shù)組，我們可以把這個數(shù)組放到外面而不是放在遞歸函數(shù)參數(shù)里里，代碼如下：

 
 
 
 
    
  
  
  
  
  1. int arr[] = {2, 3, 4, 5, 8, 10, 15, 17, 20}; 
    2.   
  
  
  
  2. int binary_search(int l, int r, int n) { 
    3.   
  
  
  
  3.     if (r >= l) { 
    4.   
  
  
  
  4.         int mid = l + (r - l) / 2; 
    5.   
  
  
  
  5.         if (arr[mid] == n) 
    6.   
  
  
  
  6.             return mid; 
    7.   
  
  
  
  7.         if (arr[mid] > n) 
    8.   
  
  
  
  8.             return binary_search(l, mid - 1, n); 
    9.   
  
  
  
  9.         return binary_search(mid + 1, r, n); 
    10.   
  
  
  
  10.     } 
    11.   
  
  
  
  11.     return -1; 
    12.   
  
  
  
  12. } 
    13.

看這份代碼將arr數(shù)組定義為全局變量，而不放在遞歸循環(huán)里，那么每層遞歸的空間復(fù)雜度是O(1)，遞歸深度為O(logn)，整體空間復(fù)雜度為 1 * logn = O(logn)。

總結(jié)

本章我們詳細分析了遞歸實現(xiàn)的求斐波那契和二分法的空間復(fù)雜度，同時也對時間復(fù)雜度做了分析。

特別是兩種遞歸實現(xiàn)的求斐波那契數(shù)列，其時間復(fù)雜度截然不容，我們還做了實驗，驗證了時間復(fù)雜度為O(2^n)是非常耗時的。

通過本篇大家應(yīng)該對遞歸算法的時間復(fù)雜度和空間復(fù)雜度有更加深刻的理解了。


本文名稱：可能對遞歸理解的還不夠！還差得遠！
URL標題：http://www.dlmjj.cn/article/dhisgih.html