趁假期復(fù)習(xí)了算法基礎(chǔ)的時(shí)間復(fù)雜度和空間復(fù)雜度，整理一遍栏尚。
原文發(fā)布于個(gè)人博客(好望角)，并在博客持續(xù)修改更新只恨，此處可能更新不及時(shí)译仗。
算法的有效性
要想理解時(shí)間復(fù)雜度和空間復(fù)雜度這兩個(gè)概念，首先要明白算法的含義坤次。
所謂算法，是解決一類問(wèn)題的通法斥赋，即一系列清晰無(wú)歧義的計(jì)算指令缰猴。
具體的，一個(gè)算法應(yīng)該有以下五個(gè)方面的特性：
- 輸入（Input）：算法必須有輸入量疤剑，用以刻畫算法的初始條件（特殊情況也可以沒(méi)有輸入量滑绒，這時(shí)算法本身定義了初始狀態(tài)）；
- 輸出（Output）：算法應(yīng)有一個(gè)或以上輸出量隘膘，輸出量是算法計(jì)算的結(jié)果疑故。沒(méi)有輸出的算法毫無(wú)意義。
- 明確性（Definiteness）：算法的描述必須無(wú)歧義弯菊，以保證算法的實(shí)際執(zhí)行結(jié)果是精確地匹配要求或期望纵势，通常要求實(shí)際運(yùn)行結(jié)果是確定的。
- 有限性（Finiteness）：算法必須在有限個(gè)步驟內(nèi)完成任務(wù)。
- 有效性（Effectiveness）：算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)（又稱可行性）钦铁。
根據(jù)以上的定義，不難發(fā)現(xiàn)。每個(gè)算法只能解決具有特定特征的一類問(wèn)題封豪。然而瓢娜，每個(gè)有固定輸入輸出的問(wèn)題可以采取多種算法來(lái)決解。
那么黎比，要怎么來(lái)比較解決同一個(gè)問(wèn)題的不同算法之間的優(yōu)劣呢超营？
這個(gè)時(shí)候，時(shí)間復(fù)雜度和空間復(fù)雜度就有了用武之地阅虫。
時(shí)間復(fù)雜度
算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)演闭，在很大程度上能很好反映出算法的優(yōu)劣與否。
驗(yàn)證算法的時(shí)間復(fù)雜度书妻，我們有以下兩個(gè)方法船响。
事后統(tǒng)計(jì)
一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的躲履，必須上機(jī)運(yùn)行測(cè)試才能知道见间。所以就有了事后統(tǒng)計(jì)的方法。
計(jì)算算法的時(shí)間復(fù)雜度工猜，往往是為了評(píng)測(cè)算法的性能米诉，設(shè)計(jì)更好的算法。這就給事后統(tǒng)計(jì)的方法帶來(lái)了兩個(gè)弊端篷帅。
- 需要先實(shí)現(xiàn)算法設(shè)計(jì)史侣，并至少運(yùn)行一次。
- 統(tǒng)計(jì)算法時(shí)間容易受到計(jì)算機(jī)硬件魏身、編程語(yǔ)言效率等環(huán)境因素影響惊橱。
事前分析
由于事后統(tǒng)計(jì)的方法有上述的弊端，我們通常采取事先估計(jì)的方法來(lái)評(píng)價(jià)算法的時(shí)間復(fù)雜度箭昵。
為了更好的比較不同算法在處理統(tǒng)一問(wèn)題上的效率税朴，通常從算法中選取一種對(duì)于所研究的問(wèn)題（或算法類型）來(lái)說(shuō)是基本操作的原操作，以該基本操作的重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度家制，記為T(n)正林。
在這里，n為輸入問(wèn)題的規(guī)模颤殴。對(duì)于同一個(gè)問(wèn)題來(lái)說(shuō)觅廓，他的輸入規(guī)模越大，往往時(shí)間復(fù)雜度也就越大涵但。
關(guān)于輸入問(wèn)題規(guī)模n杈绸，有輔助函數(shù)f(n),來(lái)統(tǒng)計(jì)算法基本操作的頻度帖蔓。因此，算法的時(shí)間復(fù)雜度往往記為蝇棉。
為了簡(jiǎn)便讨阻，我們一般在計(jì)算時(shí)間復(fù)雜度往往選取最簡(jiǎn)單的f(n)表示。例如： 篡殷，一般都只用
表示就可以了钝吮。
也就是說(shuō)，兩個(gè)算法的時(shí)間頻度不一樣板辽，但很有可能擁有相同的時(shí)間復(fù)雜度奇瘦。
例如： 與
它們的頻度不同，但時(shí)間復(fù)雜度相同劲弦，都為
耳标。
常見的算法時(shí)間復(fù)雜度由小到大依次為：
<span id="inline-green"> </span>
下面的圖片直觀的表示他們之間復(fù)雜度關(guān)系。
時(shí)間復(fù)雜度的分類
- 最壞時(shí)間復(fù)雜度：輸入數(shù)據(jù)狀態(tài)最不理想情況下的時(shí)間復(fù)雜度邑跪，也就是算法時(shí)間復(fù)雜度的上界次坡。若沒(méi)有特別聲明，時(shí)間復(fù)雜度就是指最壞時(shí)間復(fù)雜度画畅。
- 平均時(shí)間復(fù)雜度：在所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下砸琅，算法的期望時(shí)間復(fù)雜度。
- 最好時(shí)間復(fù)雜度：輸入數(shù)據(jù)狀態(tài)最理想情況下的時(shí)間復(fù)雜度轴踱。
時(shí)間復(fù)雜度預(yù)估步驟
- 找出基本語(yǔ)句：算法中執(zhí)行次數(shù)最多的那條語(yǔ)句就是基本語(yǔ)句症脂，通常是最內(nèi)層循環(huán)的循環(huán)體。
- 計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)：只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)淫僻，這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可诱篷，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析雳灵，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率棕所。
- 用O()表示算法的時(shí)間性能：將基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)放入O()中。
時(shí)間復(fù)雜度分析技巧
- 簡(jiǎn)單語(yǔ)句：程序的輸入輸出悯辙、賦值等語(yǔ)句都近似認(rèn)為需要
時(shí)間琳省。
- 順序結(jié)構(gòu)：需要依次執(zhí)行一系列語(yǔ)句所用的時(shí)間可采用O()的"求和法則"，
- 選擇結(jié)構(gòu)：如if語(yǔ)句,它的主要時(shí)間耗費(fèi)是在執(zhí)行then字句或else字句所用的時(shí)間,需注意的是檢驗(yàn)條件也需要
- 循環(huán)結(jié)構(gòu)：循環(huán)語(yǔ)句的運(yùn)行時(shí)間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗(yàn)循環(huán)條件的時(shí)間耗費(fèi),一般可用O()的"乘法法則"岛啸。
- 復(fù)雜算法：將其分成幾個(gè)容易估算的部分,然后利用求和法則和乘法法則計(jì)算整個(gè)算法的時(shí)間復(fù)雜度钓觉。
- 其他準(zhǔn)則
- 若
,則
-
, 其中C是一個(gè)正常數(shù)茴肥。
- 若
乘法法則: 是指若算法的2個(gè)部分時(shí)間復(fù)雜度分別為
和
,則
求和法則:是指若算法的2個(gè)部分時(shí)間復(fù)雜度分別為
特別地,若,
實(shí)際演練
- 三個(gè)簡(jiǎn)單語(yǔ)句，
荡灾。
Temp=i;
i=j;
j=temp;
<div class="note danger"><p> 如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)瓤狐，即使算法中有上千條語(yǔ)句瞬铸，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是础锐。</p></div>
- 因?yàn)?
嗓节，忽略低階項(xiàng)， 所以
皆警；
sum=0拦宣； （一次）
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sum++； （n^2次）
<div class="note info"><p> 一般情況下信姓，循環(huán)語(yǔ)句只需考慮循環(huán)體中語(yǔ)句的執(zhí)行次數(shù)鸵隧，忽略該語(yǔ)句中步長(zhǎng)加1、終值判別意推、控制轉(zhuǎn)移等成分豆瘫，當(dāng)有若干個(gè)循環(huán)語(yǔ)句嵌套時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的菊值。 </p></div>
- 語(yǔ)句①的頻度是
,語(yǔ)句②的頻度是
（乘法法則）, 所以
（加法法則）, 最終
, 即該程序的時(shí)間復(fù)雜度
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
- 語(yǔ)句①的頻度：2；語(yǔ)句②的頻度一般不考慮腻窒；語(yǔ)句③的頻度：n-1昵宇；語(yǔ)句④的頻度：n-1；語(yǔ)句⑤的頻度：n-1定页；
趟薄。
a=0; ①
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
- 語(yǔ)句①的頻度是1；設(shè)語(yǔ)句②的頻度是f(n), 則：
典徊。取最大值
,
i=1; ①
while (i<=n)
i=i*2;
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2; ①
}
}
空間復(fù)雜度
設(shè)計(jì)算法的時(shí)候杭煎，我們還會(huì)關(guān)注空間復(fù)雜度，空間復(fù)雜度是算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間大小的度量, 同樣是關(guān)于問(wèn)題規(guī)模n的函數(shù)卒落。
但根本上羡铲，算法的時(shí)間運(yùn)行效率才是最重要的。只要算法占用的存儲(chǔ)空間不要達(dá)到計(jì)算機(jī)無(wú)法接受的程度即可儡毕。所以也切，常常通過(guò)犧牲空間復(fù)雜度來(lái)?yè)Q取算法更加高效的運(yùn)行時(shí)間效率。
算法在計(jì)算機(jī)存儲(chǔ)器上占用的空間包括三個(gè)部分腰湾。
輸入輸出
算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間是由要解決的問(wèn)題決定的雷恃，是通過(guò)參數(shù)表由調(diào)用函數(shù)傳遞而來(lái)的，它不會(huì)隨算法的不同而改變费坊。這不是我們需要考慮的部分倒槐。
算法本身
存儲(chǔ)算法本身所占用的存儲(chǔ)空間與算法書寫的長(zhǎng)短成正比，要壓縮這部分存儲(chǔ)空間附井，就必須編寫出較短的算法讨越。然而两残，算法想要實(shí)際應(yīng)用需要根據(jù)需求采取不同的編程語(yǔ)言來(lái)實(shí)現(xiàn)，不同編程語(yǔ)言實(shí)現(xiàn)的代碼長(zhǎng)短差別很大把跨，然而存儲(chǔ)空間都在可接受范圍之內(nèi)（通常不同編程語(yǔ)言的效率更受關(guān)注）人弓。
運(yùn)行臨時(shí)占用
根據(jù)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間的不同，可以將算法分為兩類着逐。
- 原地算法（in-place algorithm）：只需要占用少量的臨時(shí)工作單元崔赌，而且不隨問(wèn)題規(guī)模的大小而改變，我們稱這種算法是“就地”進(jìn)行的耸别，是節(jié)省存儲(chǔ)的算法峰鄙。
- 非原地算法（not-in-place）：需要占用的臨時(shí)工作單元數(shù)與解決問(wèn)題的規(guī)模n有關(guān)，它隨著n的增大而增大太雨，當(dāng)n較大時(shí)吟榴，將占用較多的存儲(chǔ)單元。
算法臨時(shí)占用空間是考慮算法空間復(fù)雜度時(shí)主要考慮的部分囊扳。相比于隨著問(wèn)題輸入規(guī)模擴(kuò)大而擴(kuò)大的非原地算法吩翻，原地算法是更加簡(jiǎn)潔高效的算法（僅考慮空間復(fù)雜度時(shí)）。
實(shí)際例子
假設(shè)我們想要將擁有n個(gè)項(xiàng)目的數(shù)組反過(guò)來(lái)锥咸。一個(gè)最簡(jiǎn)單作這件事的方式是這樣：
function reverse(a[0..n])
allocate b[0..n]
for i from 0 to n
b[n - i] = a[i]
return b
不幸地狭瞎，這樣需要的空間來(lái)創(chuàng)建b數(shù)組，且配置存儲(chǔ)器通常是一件緩慢的運(yùn)算搏予。如果我們不再需要a熊锭，我們可使用這個(gè)原地算法，用它自己反轉(zhuǎn)的內(nèi)容來(lái)覆蓋掉：
function reverse-in-place(a[0..n])
for i from 0 to floor(n/2)
swap(a[i], a[n-i])
排序算法分析
了解算法的時(shí)間復(fù)雜度和空間復(fù)雜度之后雪侥，再看一些常用算法總結(jié)的時(shí)候就不會(huì)再向原來(lái)一樣有霧里探花之感了碗殷。
