算法之空間復雜度

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

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

概念

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

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

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

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

空間復雜度計算

NO.1 冒泡排序

voidBubbleSort(int*a,intn){     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)

NO.2 斐波那契數列

// 計算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銷毀后繼承了它的空間

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

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

NO.3 階乘

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

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

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

常見復雜度對比

結語

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

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