可能對(duì)遞歸理解的還不夠！還差得遠(yuǎn)！
上周小結(jié)的時(shí)候就提到了，在「算法匯總」里算法性能分析這塊還沒(méi)補(bǔ)全，后序會(huì)補(bǔ)上，所以這就來(lái)了，要分析遞歸的性能咱就分析個(gè)清清楚楚!
之前在通過(guò)一道面試題目，講一講遞歸算法的時(shí)間復(fù)雜度!中詳細(xì)講解了遞歸算法的時(shí)間復(fù)雜度，但沒(méi)有講空間復(fù)雜度。
本篇講通過(guò)求斐波那契數(shù)列和二分法再來(lái)深入分析一波遞歸算法的時(shí)間和空間復(fù)雜度，細(xì)心看完，會(huì)刷新對(duì)遞歸的認(rèn)知!
遞歸求斐波那契數(shù)列的性能分析
先來(lái)看一下求斐波那契數(shù)的遞歸寫(xiě)法。
- int fibonacci(int i) {
- if(i <= 0) return 0;
- if(i == 1) return 1;
- return fibonacci(i-1) + fibonacci(i-2);
- }
對(duì)于遞歸算法來(lái)說(shuō)，代碼一般都比較簡(jiǎn)短，從算法邏輯上看，所用的存儲(chǔ)空間也非常少，但運(yùn)行時(shí)需要內(nèi)存可不見(jiàn)得會(huì)少。
時(shí)間復(fù)雜度分析
來(lái)看看這個(gè)求斐波那契的遞歸算法的時(shí)間復(fù)雜度是多少呢?
在講解遞歸時(shí)間復(fù)雜度的時(shí)候，我們提到了遞歸算法的時(shí)間復(fù)雜度本質(zhì)上是要看: 遞歸的次數(shù) * 每次遞歸的時(shí)間復(fù)雜度。
可以看出上面的代碼每次遞歸都是O(1)的操作。再來(lái)看遞歸了多少次，這里將i為5作為輸入的遞歸過(guò)程 抽象成一顆遞歸樹(shù)，如圖：
從圖中，可以看出f(5)是由f(4)和f(3)相加而來(lái)，那么f(4)是由f(3)和f(2)相加而來(lái) 以此類(lèi)推。
在這顆二叉樹(shù)中每一個(gè)節(jié)點(diǎn)都是一次遞歸，那么這棵樹(shù)有多少個(gè)節(jié)點(diǎn)呢?
我們之前也有說(shuō)到，一棵深度(按根節(jié)點(diǎn)深度為1)為k的二叉樹(shù)最多可以有 2^k - 1 個(gè)節(jié)點(diǎn)。
所以該遞歸算法的時(shí)間復(fù)雜度為 O(2^n) ，這個(gè)復(fù)雜度是非常大的，隨著n的增大，耗時(shí)是指數(shù)上升的。
來(lái)做一個(gè)實(shí)驗(yàn)，大家可以有一個(gè)直觀的感受。
以下為C++代碼，來(lái)測(cè)一下，讓我們輸入n的時(shí)候，這段遞歸求斐波那契代碼的耗時(shí)。
- #include <iostream>
- #include <chrono>
- #include <thread>
- using namespace std;
- using namespace chrono;
- int fibonacci(int i) {
- if(i <= 0) return 0;
- if(i == 1) return 1;
- return fibonacci(i - 1) + fibonacci(i - 2);
- }
- void time_consumption() {
- int n;
- while (cin >> n) {
- milliseconds start_time = duration_cast<milliseconds >(
- system_clock::now().time_since_epoch()
- );
- fibonacci(n);
- milliseconds end_time = duration_cast<milliseconds >(
- system_clock::now().time_since_epoch()
- );
- cout << milliseconds(end_time).count() - milliseconds(start_time).count()
- <<" ms"<< endl;
- }
- }
- int main()
- {
- time_consumption();
- return 0;
- }
根據(jù)以上代碼，給出幾組實(shí)驗(yàn)數(shù)據(jù)：
測(cè)試電腦以2015版MacPro為例，CPU配置：2.7 GHz Dual-Core Intel Core i5
測(cè)試數(shù)據(jù)如下：
- n = 40，耗時(shí)：837 ms
- n = 50，耗時(shí)：110306 ms
可以看出，O(2^n)這種指數(shù)級(jí)別的復(fù)雜度是非常大的。
所以這種求斐波那契數(shù)的算法看似簡(jiǎn)潔，其實(shí)時(shí)間復(fù)雜度非常高，一般不推薦這樣來(lái)實(shí)現(xiàn)斐波那契。
其實(shí)罪魁禍?zhǔn)拙褪沁@里的兩次遞歸，導(dǎo)致了時(shí)間復(fù)雜度以指數(shù)上升。
- return fibonacci(i-1) + fibonacci(i-2);
可不可以?xún)?yōu)化一下這個(gè)遞歸算法呢。主要是減少遞歸的調(diào)用次數(shù)。
來(lái)看一下如下代碼：
- // 版本二
- int fibonacci(int first, int second, int n) {
- if (n <= 0) {
- return 0;
- }
- if (n < 3) {
- return 1;
- }
- else if (n == 3) {
- return first + second;
- }
- else {
- return fibonacci(second, first + second, n - 1);
- }
- }
這里相當(dāng)于用first和second來(lái)記錄當(dāng)前相加的兩個(gè)數(shù)值，此時(shí)就不用兩次遞歸了。
因?yàn)槊看芜f歸的時(shí)候n減1，即只是遞歸了n次，所以時(shí)間復(fù)雜度是 O(n)。
同理遞歸的深度依然是n，每次遞歸所需的空間也是常數(shù)，所以空間復(fù)雜度依然是O(n)。
代碼(版本二)的復(fù)雜度如下：
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
此時(shí)再來(lái)測(cè)一下耗時(shí)情況驗(yàn)證一下：
- #include <iostream>
- #include <chrono>
- #include <thread>
- using namespace std;
- using namespace chrono;
- int fibonacci_3(int first, int second, int n) {
- if (n <= 0) {
- return 0;
- }
- if (n < 3) {
- return 1;
- }
- else if (n == 3) {
- return first + second;
- }
- else {
- return fibonacci_3(second, first + second, n - 1);
- }
- }
- void time_consumption() {
- int n;
- while (cin >> n) {
- milliseconds start_time = duration_cast<milliseconds >(
- system_clock::now().time_since_epoch()
- );
- fibonacci_3(0, 1, n);
- milliseconds end_time = duration_cast<milliseconds >(
- system_clock::now().time_since_epoch()
- );
- cout << milliseconds(end_time).count() - milliseconds(start_time).count()
- <<" ms"<< endl;
- }
- }
- int main()
- {
- time_consumption();
- return 0;
- }
測(cè)試數(shù)據(jù)如下：
- n = 40，耗時(shí)：0 ms
- n = 50，耗時(shí)：0 ms
大家此時(shí)應(yīng)該可以看出差距了!!
空間復(fù)雜度分析
說(shuō)完了這段遞歸代碼的時(shí)間復(fù)雜度，再看看如何求其空間復(fù)雜度呢，這里給大家提供一個(gè)公式：遞歸算法的空間復(fù)雜度 = 每次遞歸的空間復(fù)雜度 * 遞歸深度
為什么要求遞歸的深度呢?
因?yàn)槊看芜f歸所需的空間都被壓到調(diào)用棧里(這是內(nèi)存管理里面的數(shù)據(jù)結(jié)構(gòu)，和算法里的棧原理是一樣的)，一次遞歸結(jié)束，這個(gè)棧就是就是把本次遞歸的數(shù)據(jù)彈出去。所以這個(gè)棧最大的長(zhǎng)度就是遞歸的深度。
此時(shí)可以分析這段遞歸的空間復(fù)雜度，從代碼中可以看出每次遞歸所需要的空間大小都是一樣的，所以每次遞歸中需要的空間是一個(gè)常量，并不會(huì)隨著n的變化而變化，每次遞歸的空間復(fù)雜度就是O(1)。
在看遞歸的深度是多少呢?如圖所示：
遞歸第n個(gè)斐波那契數(shù)的話(huà)，遞歸調(diào)用棧的深度就是n。
那么每次遞歸的空間復(fù)雜度是O(1)， 調(diào)用棧深度為n，所以這段遞歸代碼的空間復(fù)雜度就是O(n)。
- int fibonacci(int i) {
- if(i <= 0) return 0;
- if(i == 1) return 1;
- return fibonacci(i-1) + fibonacci(i-2);
- }
最后對(duì)各種求斐波那契數(shù)列方法的性能做一下分析，如題：
可以看出，求斐波那契數(shù)的時(shí)候，使用遞歸算法并不一定是在性能上是最優(yōu)的，但遞歸確實(shí)簡(jiǎn)化的代碼層面的復(fù)雜度。
二分法(遞歸實(shí)現(xiàn))的性能分析
帶大家再分析一段二分查找的遞歸實(shí)現(xiàn)。
- int binary_search( int arr[], int l, int r, int x) {
- if (r >= l) {
- int mid = l + (r - l) / 2;
- if (arr[mid] == x)
- return mid;
- if (arr[mid] > x)
- return binary_search(arr, l, mid - 1, x);
- return binary_search(arr, mid + 1, r, x);
- }
- return -1;
- }
都知道二分查找的時(shí)間復(fù)雜度是O(logn)，那么遞歸二分查找的空間復(fù)雜度是多少呢?
我們依然看 每次遞歸的空間復(fù)雜度和遞歸的深度
首先我們先明確這里的空間復(fù)雜度里面的n是什么?二分查找的時(shí)候n就是指查找數(shù)組的長(zhǎng)度，也就是代碼中的arr數(shù)組。
每次遞歸的空間復(fù)雜度可以看出主要就是參數(shù)里傳入的這個(gè)arr數(shù)組，即：O(n)。
再來(lái)看遞歸的深度，二分查找的遞歸深度是logn ，遞歸深度就是調(diào)用棧的長(zhǎng)度，那么這段代碼的空間復(fù)雜度為 n * logn = O(nlogn)。
有同學(xué)問(wèn)了：為什么網(wǎng)上很多人說(shuō)遞歸二分查找的空間復(fù)雜度是O(logn)，而不是O(nlogn)呢?
其實(shí)還是因?yàn)檫@個(gè)數(shù)組，我們可以把這個(gè)數(shù)組放到外面而不是放在遞歸函數(shù)參數(shù)里里，代碼如下：
- int arr[] = {2, 3, 4, 5, 8, 10, 15, 17, 20};
- int binary_search(int l, int r, int n) {
- if (r >= l) {
- int mid = l + (r - l) / 2;
- if (arr[mid] == n)
- return mid;
- if (arr[mid] > n)
- return binary_search(l, mid - 1, n);
- return binary_search(mid + 1, r, n);
- }
- return -1;
- }
看這份代碼將arr數(shù)組定義為全局變量，而不放在遞歸循環(huán)里，那么每層遞歸的空間復(fù)雜度是O(1)，遞歸深度為O(logn)，整體空間復(fù)雜度為 1 * logn = O(logn)。
總結(jié)
本章我們?cè)敿?xì)分析了遞歸實(shí)現(xiàn)的求斐波那契和二分法的空間復(fù)雜度，同時(shí)也對(duì)時(shí)間復(fù)雜度做了分析。
特別是兩種遞歸實(shí)現(xiàn)的求斐波那契數(shù)列，其時(shí)間復(fù)雜度截然不容，我們還做了實(shí)驗(yàn)，驗(yàn)證了時(shí)間復(fù)雜度為O(2^n)是非常耗時(shí)的。
通過(guò)本篇大家應(yīng)該對(duì)遞歸算法的時(shí)間復(fù)雜度和空間復(fù)雜度有更加深刻的理解了。
