算法之空間復(fù)雜度：衡量一個(gè)算法運(yùn)行需要開辟的額外空間

上次我們學(xué)習(xí)了時(shí)間復(fù)雜度，那么我們今天就來看看空間復(fù)雜度！

概念

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用空間大小的度量

和時(shí)間復(fù)雜度不是真的計(jì)算時(shí)間一樣，空間復(fù)雜度也不衡量算法具體占用的內(nèi)存字節(jié)數(shù)。

空間復(fù)雜度計(jì)算的是額外開辟的變量的個(gè)數(shù)，適用大O漸近法

注意：函數(shù)運(yùn)行時(shí)所需要的棧空間(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來確定。

空間復(fù)雜度計(jì)算

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;     }}

我們會(huì)發(fā)現(xiàn)，冒泡排序算法并沒有額外定義非常多的變量，一共只有3個(gè)，屬于常數(shù)階

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

其空間復(fù)雜度為O(1)

計(jì)算時(shí)注意其與N的關(guān)系

當(dāng)我們?cè)谒惴ㄖ虚_辟空間，計(jì)算空間復(fù)雜度的時(shí)候，要注意開辟的這個(gè)空間與N有沒有關(guān)系

int arr[N];//c99變長(zhǎng)數(shù)組，和傳過來的參數(shù)有關(guān)int*a=(int*)malloc(sizeof(int)*N);//和傳過來的參數(shù)有關(guān)，O(N)int* a=(int*)malloc(sizeof(int)*3);//和傳過來的參數(shù)無關(guān)，O(1)

NO.2 斐波那契數(shù)列

// 計(jì)算Fibonacci的空間復(fù)雜度？// 返回斐波那契數(shù)列的前n項(xiàng)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;}

和上面的斐波那契數(shù)列的遞歸代碼不同，這里我們新創(chuàng)建了一個(gè)數(shù)組，用來保存計(jì)算出來的斐波那契數(shù)

一共malloc了n+1個(gè)長(zhǎng)整型的空間，空間復(fù)雜度是O(N)

空間重復(fù)使用問題

如果是遞歸方法的斐波那契算法，其空間復(fù)雜度是多少呢？

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

答案也是O(N)

因?yàn)閷?duì)于遞歸算法而言，其開辟的函數(shù)棧幀空間是可以重復(fù)利用的！

如fib(8)的調(diào)用，其開辟的函數(shù)棧幀，是可以在后續(xù)繼續(xù)調(diào)用fib函數(shù)時(shí)重復(fù)使用的

上圖中f1和f2是兩個(gè)函數(shù)，但執(zhí)行了相同的功能。其函數(shù)調(diào)用的空間實(shí)際上是一個(gè)，f2在f1銷毀后繼承了它的空間

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

不過由于斐波那契數(shù)的遞歸算法會(huì)遞歸非常多次，在數(shù)字很大的時(shí)候，會(huì)導(dǎo)致棧溢出

NO.3 階乘

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

雖然函數(shù)本身的空間不計(jì)入時(shí)間復(fù)雜度，這里計(jì)算的是遞歸調(diào)用時(shí)額外開辟的函數(shù)棧幀空間

一共調(diào)用了N-1次，每個(gè)棧幀使用了常數(shù)個(gè)空間，空間復(fù)雜度是O(N)

常見復(fù)雜度對(duì)比

結(jié)語

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

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