1.3 算法的描述和算法分析

1.3.1 算法的描述

算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。一個(gè)算法具有以下5個(gè)重要的特性。

1. 有窮性

一個(gè)算法必須總是在執(zhí)行有窮步（對(duì)任何合法的輸入值）之后，且每一步都可在有窮時(shí)間內(nèi)完成。即一個(gè)算法對(duì)于任意一組合法輸入值，在執(zhí)行有窮步之后一定能夠結(jié)束。

2. 確定性

算法中每一條指令都必須有確切的含義，使讀者在理解時(shí)不會(huì)產(chǎn)生二義性。同時(shí)，在任何條件下，算法都只有一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的結(jié)果。

3. 可行性

算法中所描述的操作必須足夠基本，且都可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。

4. 輸入

作為算法加工對(duì)象的量值，一個(gè)算法有0個(gè)或多個(gè)輸入。有的量值需要在算法執(zhí)行過程中輸入，而有的算法表面上沒有輸入，實(shí)際上已經(jīng)被嵌入算法中。

5. 輸出

輸出是一組同“輸入”有確定對(duì)應(yīng)關(guān)系的量值，是算法進(jìn)行信息加工后所得到的產(chǎn)物，一個(gè)算法可以有一個(gè)或多個(gè)輸出。

設(shè)計(jì)一個(gè)算法時(shí)，它應(yīng)該滿足以下4個(gè)要求。

（1）正確性

要求算法能夠正確地實(shí)現(xiàn)預(yù)先規(guī)定的功能和滿足性能要求，這是最重要也是最基本的標(biāo)準(zhǔn)。目前大多數(shù)算法是用自然語言描述需求的，它至少應(yīng)包括輸入、輸出和加工處理等的明確無歧義的描述。設(shè)計(jì)或選擇算法應(yīng)當(dāng)能正確地反映這種需求。

（2）可讀性

算法應(yīng)當(dāng)易于理解，可讀性強(qiáng)。為了達(dá)到這個(gè)要求，算法必須做到邏輯清晰、簡(jiǎn)單并且結(jié)構(gòu)化?；逎y懂的程序容易隱藏較多錯(cuò)誤，難以調(diào)試和修改。

（3）健壯性

算法要求具有良好的容錯(cuò)性，能夠提供異常處理，能夠?qū)斎脒M(jìn)行檢查。不經(jīng)常產(chǎn)生異常中斷或死機(jī)現(xiàn)象。例如，一個(gè)求矩形面積的算法，當(dāng)輸入的坐標(biāo)集合不能構(gòu)成一個(gè)矩形時(shí)，不應(yīng)繼續(xù)計(jì)算，而應(yīng)當(dāng)報(bào)告輸入錯(cuò)誤。同時(shí)，處理錯(cuò)誤的方法是返回一個(gè)表示錯(cuò)誤的值，而不是輸出錯(cuò)誤信息或直接異常中斷。

（4）效率與低存儲(chǔ)量要求

通常算法的效率主要指算法的執(zhí)行時(shí)間。對(duì)于同一個(gè)問題，如果能用多種算法進(jìn)行求解，執(zhí)行時(shí)間短的算法效率高。算法存儲(chǔ)量指的是算法執(zhí)行過程中所需的存儲(chǔ)空間。效率與低存儲(chǔ)量要求這兩者都與問題的規(guī)模有關(guān)。例如，求100個(gè)學(xué)生的平均成績(jī)和求10000個(gè)學(xué)生的平均成績(jī)?cè)跁r(shí)間和空間的成本上必然是存在差異的。