3．空間復(fù)雜度
空間復(fù)雜度也是一個數(shù)學(xué)表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度。
空間復(fù)雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復(fù)雜度算的是變量的個數(shù)。空間復(fù)雜度計算規(guī)則基本跟實踐復(fù)雜度類似，也使用大O漸進表示法。

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

我們直接上例題來講解

void lystyle(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;}
}

首先我們要思考一下void lystyle(int*a;int n)這個函數(shù)聲明中創(chuàng)建的a和n算不算到空間復(fù)雜度里面去，顯然是不用的

空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。（計算的是函數(shù)額外創(chuàng)建的變量個數(shù)）

這整個函數(shù)里面一共創(chuàng)建了三個變量分別是exchange，i，n占用的內(nèi)存是不同的

因此創(chuàng)建變量是常數(shù)個，O(1)這個地方不知道為啥是O(1)可以看上一期的暑期數(shù)據(jù)結(jié)構(gòu) 時間復(fù)雜度-CSDN博客

我們接下來看一個很有意思的事

但是為啥會導(dǎo)致這樣呢？

原因在于我們使用函數(shù)時會開辟一片空間，函數(shù)結(jié)束時會將那片空間還給系統(tǒng) ，但是下次另一個函數(shù)使用時開辟的那個空間還是原來函數(shù)的

那么還是上一期的函數(shù)（時間復(fù)雜度我會放到每日一題以一個數(shù)學(xué)專業(yè)的學(xué)生去講解）

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

那么這個地方的空間復(fù)雜度是多少呢？

有人可能說是O（0）但是只有函數(shù)本身聲明中的變量才不算入空間復(fù)雜度里面，但是遞歸產(chǎn)生的變量會被算到時間復(fù)雜度里面

那么還有人可能說和時間復(fù)雜度一樣是O(N*N)，因為我每遞歸一次就執(zhí)行了一次語句

但是結(jié)果也不對

那么答案是多少呢？

答案是O（N）

這個地方遞歸執(zhí)行是有順序的

這個地方return Fib(N - 1) + Fib(N - 2);

要先計算Fib(N - 1)再計算Fib(N - 2);

要計算Fib(N - 1)就要先算Fib(N - 2)+Fib(N -3 )

遞歸是一步一步實現(xiàn)的，不遇到return 不停止我們以N=6來畫一個計算的過程圖

這個地方我們看箭頭4和5，我們先執(zhí)行函數(shù)Fib(3)使用完之后函數(shù)空間還給系統(tǒng)，但是執(zhí)行Fib(4)本質(zhì)上再開辟的那個空間還是和Fib(3)一樣的

因此這個地方同一深度的函數(shù)的是同一片空間（深度從上到下看）

因此這個地方的空間復(fù)雜度就是O（N）(我么只看最左側(cè)看它最深度有多深就行)