前言

　　在上一篇文章中，耀哥給大家介紹了時間復(fù)雜度的概念，這一次耀哥將會給大家介紹評價算法優(yōu)劣的另一個評測標(biāo)準(zhǔn)---空間復(fù)雜度。

　　一. 空間復(fù)雜度的概念

　　空間復(fù)雜度(Space Complexity)，是對一個算法在運行過程中臨時占用存儲空間大小的量度。值得注意的是，時間復(fù)雜度不是用來計算程序具體耗時的，空間復(fù)雜度也不是用來計算程序所占的具體內(nèi)存大小，它們都只是一個量度而已。

　　二. 常見的空間復(fù)雜度

　常數(shù)階O(1)

　　int sum = 0;

　　for(int i=0;i<n;i++){< p="">

　　sum=sum+i;

　　}

 　　此例中，不管n變得多大，都只有2個變量占用內(nèi)存，內(nèi)存的占用是一個常數(shù)，記住O(1)即可。

　　O(n)

　　int sum = 0;

　　for(int i=0;i<n;i++){< p="">

　　sum=sum+i;

　　int m = sum;

　　}

 　　我們注意看此案例中，在for循壞中，變量m一共被聲明了n次，再加上sum與i的聲明，一共分配的內(nèi)存有n+2次。其中，2可以忽略，所以算法的空間復(fù)雜度為O(n)

　O(Log2N)

 　　另一個常見的空間復(fù)雜度是O(Log2N)，我們來看看下面這段代碼，它的空間復(fù)雜度就是O(Log2N)，大家自己考慮一下是不是這樣?　

　int sum = 0;

　　for(int i=0;i<n;i++){< p="">

　　sum=sum+i;

　　int m = sum;

　　i= 2*i;

　　}

 　　三. 結(jié)語

　　經(jīng)過以上幾個案例，耀哥大致給同學(xué)們介紹了一下常見的幾種空間復(fù)雜度。值得注意的是，隨著計算機(jī)行業(yè)的迅速發(fā)展，計算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不再需要特別關(guān)注一個算法的空間復(fù)雜度，大多數(shù)時候都是用空間換取時間。但如果是某些存儲容量比較小的微控制器，例如單片機(jī)等，還是需要考慮一下空間復(fù)雜度的。