常用的排序算法的時(shí)間復(fù)雜度與空間復(fù)雜度
1、時(shí)間復(fù)雜度
（1）時(shí)間頻度 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間捺氢，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試虽界，只需知道哪個(gè)算法花費(fèi)的時(shí) 間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了涛菠。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例莉御，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多撇吞，它花費(fèi)時(shí)間就多。一個(gè)算法中的 語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度礁叔。記為T(n)牍颈。
（2）時(shí)間復(fù)雜度 在剛才提到的時(shí)間頻度中，n稱為問題的規(guī)模琅关，當(dāng)n不斷變化時(shí)煮岁，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律涣易。為此画机，我們引入時(shí)間 復(fù)雜度概念。 一般情況下新症，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)步氏，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大 時(shí)徒爹，T（n)/f(n)的極限值為不等于零的常數(shù)荚醒，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度隆嗅，簡(jiǎn)稱時(shí)間復(fù)雜度界阁。
在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)榛瓮，則時(shí)間復(fù)雜度為O(1),另 外铺董，在時(shí)間頻度不相同時(shí)，時(shí)間復(fù)雜度有可能相同禀晓，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同精续，但時(shí)間復(fù)雜度相同，都為 O(n2)粹懒。 按數(shù)量級(jí)遞增排列重付，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1),對(duì)數(shù)階O(log2n),線性階O(n), 線性對(duì)數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...凫乖， k次方階O(nk),指數(shù)階O(2n)确垫。隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大帽芽，算法的執(zhí)行效率越低删掀。 2、空間復(fù)雜度 與時(shí)間復(fù)雜度類似导街，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量披泪。記作: S(n)=O(f(n)) 我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲(chǔ)單元規(guī)模。討論方法與時(shí)間復(fù)雜度類似搬瑰，不再贅述款票。
（3）漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能 主要用算法時(shí)間復(fù)雜度的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能控硼。
2、類似于時(shí)間復(fù)雜度的討論艾少，一個(gè)算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間卡乾，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度缚够。
空 間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度幔妨。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ) 空間谍椅，算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面陶冷。算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間是由要解決的問題決定 的，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來(lái)的毯辅，它不隨本算法的不同而改變。存儲(chǔ)算法本身所占用的存儲(chǔ)空間與算法書寫的長(zhǎng)短成正比煞额，要壓縮這方面的存儲(chǔ)空間思恐，就必 須編寫出較短的算法。算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間隨算法的不同而異膊毁，有的算法只需要占用少量的臨時(shí)工作單元胀莹，而且不隨問題規(guī)模的大小而改變，我們 稱這種算法是“就地/"進(jìn)行的婚温，是節(jié)省存儲(chǔ)的算法描焰，如這一節(jié)介紹過的幾個(gè)算法都是如此；有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模n有關(guān)栅螟，它隨著 n的增大而增大荆秦，當(dāng)n較大時(shí)，將占用較多的存儲(chǔ)單元力图，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況步绸。
如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)吃媒，可表示為O(1)瓤介；當(dāng) 一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)，可表示為0(10g2n)赘那；當(dāng)一個(gè)算法的空I司復(fù)雜度與n成線性比例關(guān)系時(shí)刑桑，可表示為0(n).若形 參為數(shù)組，則只需要為它分配一個(gè)存儲(chǔ)由實(shí)參傳送來(lái)的一個(gè)地址指針的空間募舟，即一個(gè)機(jī)器字長(zhǎng)空間祠斧；若形參為引用方式，則也只需要為其分配存儲(chǔ)一個(gè)地址的空間胃珍， 用它來(lái)存儲(chǔ)對(duì)應(yīng)實(shí)參變量的地址梁肿，以便由系統(tǒng)自動(dòng)引用實(shí)參變量蜓陌。
