【算法】幾分鐘時(shí)間讓你徹底學(xué)會(huì)—空間復(fù)雜度！
算法之空間復(fù)雜度：衡量一個(gè)算法運(yùn)行需要開(kāi)辟的額外空間
上次我們學(xué)習(xí)了時(shí)間復(fù)雜度，那么我們今天就來(lái)看看空間復(fù)雜度！
概念
空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用空間大小的度量
和時(shí)間復(fù)雜度不是真的計(jì)算時(shí)間一樣，空間復(fù)雜度也不衡量算法具體占用的內(nèi)存字節(jié)數(shù)。
空間復(fù)雜度計(jì)算的是額外開(kāi)辟的變量的個(gè)數(shù)，適用大O漸近法
注意：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過(guò)函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來(lái)確定。
空間復(fù)雜度計(jì)算
NO.1 冒泡排序
我們會(huì)發(fā)現(xiàn)，冒泡排序算法并沒(méi)有額外定義非常多的變量，一共只有3個(gè)，屬于常數(shù)階
其空間復(fù)雜度為O(1)
計(jì)算時(shí)注意其與N的關(guān)系
當(dāng)我們?cè)谒惴ㄖ虚_(kāi)辟空間，計(jì)算空間復(fù)雜度的時(shí)候，要注意開(kāi)辟的這個(gè)空間與N有沒(méi)有關(guān)系
NO.2 斐波那契數(shù)列
和上面的斐波那契數(shù)列的遞歸代碼不同，這里我們新創(chuàng)建了一個(gè)數(shù)組，用來(lái)保存計(jì)算出來(lái)的斐波那契數(shù)
一共malloc了n+1個(gè)長(zhǎng)整型的空間，空間復(fù)雜度是O(N)
空間重復(fù)使用問(wèn)題
如果是遞歸方法的斐波那契算法，其空間復(fù)雜度是多少呢？
答案也是O(N)
因?yàn)閷?duì)于遞歸算法而言，其開(kāi)辟的函數(shù)棧幀空間是可以重復(fù)利用的！
如fib(8)的調(diào)用，其開(kāi)辟的函數(shù)棧幀，是可以在后續(xù)繼續(xù)調(diào)用fib函數(shù)時(shí)重復(fù)使用的
上圖中f1和f2是兩個(gè)函數(shù)，但執(zhí)行了相同的功能。其函數(shù)調(diào)用的空間實(shí)際上是一個(gè)，f2在f1銷毀后繼承了它的空間
這就好比每一次新的遞歸都會(huì)開(kāi)一家新的飯店，但是你下次還想吃東北菜的時(shí)候，可以去之前開(kāi)的東北菜館，咱沒(méi)必要讓別人再開(kāi)一家館子不是嘛？
不過(guò)由于斐波那契數(shù)的遞歸算法會(huì)遞歸非常多次，在數(shù)字很大的時(shí)候，會(huì)導(dǎo)致棧溢出
NO.3 階乘
雖然函數(shù)本身的空間不計(jì)入時(shí)間復(fù)雜度，這里計(jì)算的是遞歸調(diào)用時(shí)額外開(kāi)辟的函數(shù)棧幀空間
一共調(diào)用了N-1次，每個(gè)棧幀使用了常數(shù)個(gè)空間，空間復(fù)雜度是O(N)
常見(jiàn)復(fù)雜度對(duì)比
結(jié)語(yǔ)
時(shí)間復(fù)雜度和空間復(fù)雜度可以幫我們很好的了解自己所寫算法的好壞，在未來(lái)面試的時(shí)候，HR肯定也更喜歡效率高的算法
要多刷題，好好積累自己的能力，想必之后寫出好算法也是水到渠成（吧？）
-----------------------------------
51CTO丨作者：慕雪年華
為了幫助大家，輕松，高效學(xué)習(xí)C語(yǔ)言/C++,給大家分享我收集的資源，從最零基礎(chǔ)開(kāi)始的,幫助大家在學(xué)習(xí)C語(yǔ)言的道路上披荊斬棘！
微信公眾號(hào)：C語(yǔ)言編程學(xué)習(xí)基地
整理分享（多年學(xué)習(xí)的源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）最重要的是你可以在群里面交流提問(wèn)編程問(wèn)題哦！
歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長(zhǎng)比自己琢磨更快哦！大家也要把握住有限的時(shí)光，抓住成長(zhǎng)的每一次機(jī)會(huì)哦~
編程學(xué)習(xí)書籍分享：
粉絲編程交流：
