前言

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

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

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

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

　常數(shù)階O(1)

　　int sum = 0;

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

　　sum=sum+i;

　　}

 　　此例中，不管n變得多大，都只有2個(gè)變量占用內(nèi)存，內(nèi)存的占用是一個(gè)常數(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)

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

　int sum = 0;

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

　　sum=sum+i;

　　int m = sum;

　　i= 2*i;

　　}

 　　三. 結(jié)語(yǔ)

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