考點(diǎn)精講

1.1　算　法

考點(diǎn)1　算法的基本概念

（1）算法的定義

算法是指解題方案的準(zhǔn)確而完整的描述，即算法是對(duì)特定問(wèn)題求解步驟的一種描述。它是一組嚴(yán)謹(jǐn)定義運(yùn)算順序的規(guī)則，且每個(gè)規(guī)則都是明確有效的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。需要注意的是：算法不等于程序，也不等于計(jì)算方法。

（2）算法的基本特征

①可行性

a．算法中的每一步驟都必須能夠?qū)崿F(xiàn)；

b．算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。

②確定性

確定性是指算法中的每一個(gè)步驟都必須有明確的定義，不允許有模棱兩可的解釋，也不允許有多義性。

③有窮性

有窮性是指算法必須能在有限的時(shí)間內(nèi)做完，即必須能在執(zhí)行有限個(gè)步驟之后終止，且必須有合理的執(zhí)行時(shí)間。

④擁有足夠的情報(bào)

算法是否有效，取決于為算法所提供的情報(bào)是否足夠。一般而言，當(dāng)算法有足夠的情報(bào)時(shí)，此算法有效，而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無(wú)效。

【真題演練】

算法的有窮性是指（　　）。[2013年9月真題]

A．算法程序的運(yùn)行時(shí)間是有限的

B．算法程序所處理的數(shù)據(jù)量是有限的

C．算法程序的長(zhǎng)度是有限的

D．算法只能被有限的用戶使用

【答案】A

【解析】算法設(shè)計(jì)有窮性要求操作步驟有限且必須在有限時(shí)間內(nèi)完成，耗費(fèi)太長(zhǎng)時(shí)間得到的正確結(jié)果是沒(méi)有意義的。答案選擇A選項(xiàng)。

考點(diǎn)2　算法設(shè)計(jì)基本方法

（1）列舉法

①基本思想

根據(jù)提出的問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰模男┦遣恍枰摹３Ｓ糜诮鉀Q“是否存在”或“有多少種可能”等類型的問(wèn)題。

②主要特點(diǎn)

算法比較簡(jiǎn)單，但列舉情況較多時(shí)，算法工作量很大。

③注意事項(xiàng)

例舉算法時(shí)，通過(guò)對(duì)實(shí)際問(wèn)題進(jìn)行詳細(xì)分析，將與問(wèn)題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，并從中找出規(guī)律，或?qū)λ锌赡艿那闆r進(jìn)行分類，從而引出一些有用的信息，減少列舉量。

（2）歸納法

①基本思想

通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。

②主要特點(diǎn)

a．比列舉法更能反映問(wèn)題的本質(zhì)，可解決列舉量為無(wú)限的問(wèn)題；

b．可操作性低，不易歸納出一個(gè)具體數(shù)學(xué)模型；

c．歸納得出的結(jié)論只是一種猜測(cè)，須對(duì)這種猜測(cè)加以必要的證明。

（3）遞推

①基本思想

從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。

②主要特點(diǎn)

a．初始條件或問(wèn)題本身已給定，或通過(guò)對(duì)問(wèn)題的分析化簡(jiǎn)得到；

b．遞推本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果；

c．?dāng)?shù)值型遞推算法計(jì)算過(guò)程中必須注意數(shù)值計(jì)算的穩(wěn)定性問(wèn)題。

（4）遞歸

①基本思想

將復(fù)雜問(wèn)題逐層分解，歸結(jié)為一些簡(jiǎn)單的問(wèn)題，將簡(jiǎn)單問(wèn)題解決掉，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合。

②主要特點(diǎn)

a．遞歸的基礎(chǔ)是歸納，對(duì)問(wèn)題逐層分解的過(guò)程實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解；

b．在可計(jì)算性理論和算法設(shè)計(jì)中占有重要地位；

c．遞歸算法比遞推算法清晰易讀，結(jié)構(gòu)簡(jiǎn)練；

d．設(shè)計(jì)遞歸算法比遞推算法容易，但是其執(zhí)行效率較低。

③分類

a．直接遞歸。一個(gè)算法P顯式地調(diào)用自己。

b．間接遞歸。算法P調(diào)用另一個(gè)算法Q，而算法Q又調(diào)用算法P。

④遞歸與遞推的區(qū)別

遞歸與遞推的區(qū)別主要在于二者實(shí)現(xiàn)方法的不同，表現(xiàn)為：

a．遞歸是從算法本身到達(dá)遞歸的邊界的；

b．遞推是從初始條件出發(fā)，逐次推出所需求的結(jié)果。

（5）減半遞推技術(shù)

減半遞推技術(shù)是工程上常用的分治法，其中，“減半”指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變；“遞推”指重復(fù)“減半”的過(guò)程。

（6）回溯法

回溯法是指通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，若試探成功，則問(wèn)題得到解決，若試探失敗，則逐步回退換別的路線再進(jìn)行試探。

【真題演練】

1下列敘述中正確的是（　　）。[2013年9月真題]

A．所謂算法就是計(jì)算方法

B．程序可以作為算法的一種描述方法

C．算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果

D．算法設(shè)計(jì)可以忽略算法的運(yùn)算時(shí)間

【答案】B

【解析】A項(xiàng)錯(cuò)誤，算法并不等同于計(jì)算方法，是指對(duì)解題方案的準(zhǔn)確而完整的描述；C項(xiàng)錯(cuò)誤，算法設(shè)計(jì)需要考慮可行性、確定性、有窮性與足夠的情報(bào)；D項(xiàng)錯(cuò)誤，算法設(shè)計(jì)有窮性要求操作步驟有限且必須在有限時(shí)間內(nèi)完成，耗費(fèi)太長(zhǎng)時(shí)間得到的正確結(jié)果是沒(méi)有意義的；B項(xiàng)正確，程序可以作為算法的一種描述方法,算法在實(shí)現(xiàn)時(shí)需要用具體的程序設(shè)計(jì)語(yǔ)言描述。答案選擇B選項(xiàng)。

2下列關(guān)于算法的描述中錯(cuò)誤的是（　　）。[2014年3月真題]

A．算法強(qiáng)調(diào)動(dòng)態(tài)的執(zhí)行過(guò)程，不同于靜態(tài)的計(jì)算公式

B．算法必須能在有限個(gè)步驟之后終止

C．算法設(shè)計(jì)必須考慮算法的復(fù)雜度

D．算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境

【答案】D

【解析】算法是指對(duì)解題方案的準(zhǔn)確而完整的描述。A項(xiàng)正確，算法強(qiáng)調(diào)實(shí)現(xiàn)，不同于數(shù)學(xué)上的計(jì)算方法；B項(xiàng)正確，算法的有窮性是指，算法中的操作步驟為有限個(gè)，且每個(gè)步驟都能在有限時(shí)間內(nèi)完成；C項(xiàng)正確，算法設(shè)計(jì)必須考慮執(zhí)行算法所需要的資源，即時(shí)間復(fù)雜度與空間復(fù)雜度；D項(xiàng)錯(cuò)誤，算法的優(yōu)劣取決于算法復(fù)雜度，只有當(dāng)算法被編程實(shí)現(xiàn)運(yùn)行時(shí)才會(huì)受到運(yùn)行環(huán)境影響。答案選擇D選項(xiàng)。

考點(diǎn)3　算法復(fù)雜度

（1）時(shí)間復(fù)雜度

①定義

算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即：算法的工作量＝f（n），其中，n是問(wèn)題的規(guī)模。

②在同一問(wèn)題規(guī)模下，若算法的基本運(yùn)算次數(shù)取決于某一特定輸入，可用以下兩種方法來(lái)分析算法的工作量：

a．平均性態(tài)

平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。算法的平均性態(tài)定義為：

其中，x是所有可能輸入中的某個(gè)特定輸入，p（x）是x出現(xiàn)的概率，即輸入為x的概率，t（x）是算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，D_n表示當(dāng)規(guī)模為n時(shí)，算法執(zhí)行時(shí)所有可能輸入的集合。

b．最壞情況復(fù)雜性

最壞情況分析是指規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。其定義為：

（2）空間復(fù)雜度

①定義

算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

②存儲(chǔ)空間組成

一個(gè)算法的存儲(chǔ)空間包括以下幾種：

a．算法程序占用的空間；

b．輸入的初始數(shù)據(jù)占用的存儲(chǔ)空間；

c．算法執(zhí)行過(guò)程中所需要的額外空間。

額外空間包括算法程序執(zhí)行過(guò)程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間，若額外空間相對(duì)于問(wèn)題規(guī)模來(lái)說(shuō)是常數(shù)，則稱該算法是原地工作的。

【真題演練】

1下列敘述中正確的是（　　）。[2015年3月真題]

A．算法的效率只與問(wèn)題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)

B．算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量

C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的

D．算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)

【答案】B

【解析】A項(xiàng)錯(cuò)誤的，效率與存儲(chǔ)結(jié)構(gòu)有密切關(guān)系。B項(xiàng)正確，算法的時(shí)間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需時(shí)間的度量。C項(xiàng)錯(cuò)誤，邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是兩個(gè)概念不可能一一對(duì)應(yīng)的。D項(xiàng)錯(cuò)誤，算法的時(shí)間復(fù)雜度與空間復(fù)雜度是獨(dú)立的。答案選擇B選項(xiàng)。

2算法的空間復(fù)雜度是指（　　）。[2013年9月真題]

A．算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間

B．算法所處理的數(shù)據(jù)量

C．算法程序中的語(yǔ)句或指令條數(shù)

D．算法在執(zhí)行過(guò)程中所需要的臨時(shí)工作單元數(shù)

【答案】A

【解析】算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間。包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過(guò)程中所需要的額外空間。答案選擇A選項(xiàng)。

3算法空間復(fù)雜度的度量方法是（　　）。[2014年9月真題]

A．算法程序的長(zhǎng)度

B．算法所處理的數(shù)據(jù)量

C．執(zhí)行算法所需要的工作單元

D．執(zhí)行算法所需要的存儲(chǔ)空間

【答案】D

【解析】算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間。包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過(guò)程中所需要的額外空間。答案選擇D選項(xiàng)。