算法之空間複雜度：衡量一個算法運行需要開辟的額外空間

上次我們學習了時間複雜度，那麼我們今天就來看看空間複雜度！

空間複雜度是對一個算法在運行過程中臨時占用空間大小的度量

和時間複雜度不是真的計算時間一樣，空間複雜度也不衡量算法具體占用的内存字節數。

空間複雜度計算的是額外開辟的變量的個數，适用大O漸近法

注意：函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經确定好了，因此空間複雜度主要通過函數在運行時候顯式申請的額外空間來确定。

void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }

我們會發現，冒泡排序算法并沒有額外定義非常多的變量，一共隻有3個，屬于常數階

size_t end = n; int exchange = 0; size_t i = 1;

其空間複雜度為​​O(1)​​

計算時注意其與N的關系

當我們在算法中開辟空間，計算空間複雜度的時候，要注意開辟的這個空間與N有沒有關系

int arr[N];//c99變長數組，和傳過來的參數有關 int* a=(int*)malloc(sizeof(int)*N);//和傳過來的參數有關，O(N)​ int* a=(int*)malloc(sizeof(int)*3);//和傳過來的參數無關，O(1)​

// 計算Fibonacci的空間複雜度？ // 返回斐波那契數列的前n項 long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n 1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; i) { fibArray[i] = fibArray[i - 1] fibArray [i - 2]; } return fibArray; }

和上面的斐波那契數列的遞歸代碼不同，這裡我們新創建了一個數組，用來保存計算出來的斐波那契數

一共malloc了n 1個長整型的空間，空間複雜度是O(N)

空間重複使用問題

如果是遞歸方法的斐波那契算法，其空間複雜度是多少呢？

long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) Fib(N-2); }

答案也是O(N)

因為對于遞歸算法而言，其開辟的函數棧幀空間是可以重複利用的！

如fib(8)的調用，其開辟的函數棧幀，是可以在後續繼續調用fib函數時重複使用的

上圖中f1和f2是兩個函數，但執行了相同的功能。其函數調用的空間實際上是一個，f2在f1銷毀後繼承了它的空間

這就好比每一次新的遞歸都會開一家新的飯店，但是你下次還想吃東北菜的時候，可以去之前開的東北菜館，咱沒必要讓别人再開一家館子不是嘛？

不過由于斐波那契數的遞歸算法會遞歸非常多次，在數字很大的時候，會導緻棧溢出

long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }

雖然函數本身的空間不計入時間複雜度，這裡計算的是遞歸調用時額外開辟的函數棧幀空間

一共調用了N-1次，每個棧幀使用了常數個空間，空間複雜度是O(N)

時間複雜度和空間複雜度可以幫我們很好的了解自己所寫算法的好壞，在未來面試的時候，HR肯定也更喜歡效率高的算法

要多刷題，好好積累自己的能力，想必之後寫出好算法也是水到渠成（吧？）

-----------------------------------

51CTO丨作者：慕雪年華

為了幫助大家，輕松，高效學習C語言/C ,給大家分享我收集的資源，從最零基礎開始的,幫助大家在學習C語言的道路上披荊斬棘！

編程學習書籍分享：

編程學習視頻分享：

整理分享（多年學習的源碼、項目實戰視頻、項目筆記，基礎入門教程）最重要的是你可以在群裡面交流提問編程問題哦！

對于C/C 感興趣可以關注小編在後台私信我：【編程交流】一起來學習哦！可以領取一些C/C 的項目學習視頻資料哦！已經設置好了關鍵詞自動回複，自動領取就好了！