考點精講

1.1　算　法

考點1　算法的基本概念

（1）算法的定義

算法是指解題方案的準確而完整的描述，即算法是對特定問題求解步驟的一種描述。它是一組嚴謹定義運算順序的規(guī)則，且每個規(guī)則都是明確有效的，此順序將在有限的次數下終止。需要注意的是：算法不等于程序，也不等于計算方法。

（2）算法的基本特征

①可行性

a．算法中的每一步驟都必須能夠實現；

b．算法執(zhí)行的結果要能夠達到預期的目的。

②確定性

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

③有窮性

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

④擁有足夠的情報

算法是否有效，取決于為算法所提供的情報是否足夠。一般而言，當算法有足夠的情報時，此算法有效，而當提供的情報不夠時，算法可能無效。

【真題演練】

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

A．算法程序的運行時間是有限的

B．算法程序所處理的數據量是有限的

C．算法程序的長度是有限的

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

【答案】A

【解析】算法設計有窮性要求操作步驟有限且必須在有限時間內完成，耗費太長時間得到的正確結果是沒有意義的。答案選擇A選項。

考點2　算法設計基本方法

（1）列舉法

①基本思想

根據提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。常用于解決“是否存在”或“有多少種可能”等類型的問題。

②主要特點

算法比較簡單，但列舉情況較多時，算法工作量很大。

③注意事項

例舉算法時，通過對實際問題進行詳細分析，將與問題有關的知識條理化、完備化、系統(tǒng)化，并從中找出規(guī)律，或對所有可能的情況進行分類，從而引出一些有用的信息，減少列舉量。

（2）歸納法

①基本思想

通過列舉少量的特殊情況，經過分析，最后找出一般的關系。

②主要特點

a．比列舉法更能反映問題的本質，可解決列舉量為無限的問題；

b．可操作性低，不易歸納出一個具體數學模型；

c．歸納得出的結論只是一種猜測，須對這種猜測加以必要的證明。

（3）遞推

①基本思想

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

②主要特點

a．初始條件或問題本身已給定，或通過對問題的分析化簡得到；

b．遞推本質上屬于歸納法，遞推關系式往往是歸納的結果；

c．數值型遞推算法計算過程中必須注意數值計算的穩(wěn)定性問題。

（4）遞歸

①基本思想

將復雜問題逐層分解，歸結為一些簡單的問題，將簡單問題解決掉，再沿著原來分解的逆過程逐步進行綜合。

②主要特點

a．遞歸的基礎是歸納，對問題逐層分解的過程實際上并沒有對問題進行求解；

b．在可計算性理論和算法設計中占有重要地位；

c．遞歸算法比遞推算法清晰易讀，結構簡練；

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

③分類

a．直接遞歸。一個算法P顯式地調用自己。

b．間接遞歸。算法P調用另一個算法Q，而算法Q又調用算法P。

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

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

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

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

（5）減半遞推技術

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

（6）回溯法

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

【真題演練】

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

A．所謂算法就是計算方法

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

C．算法設計只需考慮得到計算結果

D．算法設計可以忽略算法的運算時間

【答案】B

【解析】A項錯誤，算法并不等同于計算方法，是指對解題方案的準確而完整的描述；C項錯誤，算法設計需要考慮可行性、確定性、有窮性與足夠的情報；D項錯誤，算法設計有窮性要求操作步驟有限且必須在有限時間內完成，耗費太長時間得到的正確結果是沒有意義的；B項正確，程序可以作為算法的一種描述方法,算法在實現時需要用具體的程序設計語言描述。答案選擇B選項。

2下列關于算法的描述中錯誤的是（　　）。[2014年3月真題]

A．算法強調動態(tài)的執(zhí)行過程，不同于靜態(tài)的計算公式

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

C．算法設計必須考慮算法的復雜度

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

【答案】D

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

考點3　算法復雜度

（1）時間復雜度

①定義

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

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

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

a．平均性態(tài)

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

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

b．最壞情況復雜性

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

（2）空間復雜度

①定義

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

②存儲空間組成

一個算法的存儲空間包括以下幾種：

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

b．輸入的初始數據占用的存儲空間；

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

額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數據結構所需要的附加存儲空間，若額外空間相對于問題規(guī)模來說是常數，則稱該算法是原地工作的。

【真題演練】

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

A．算法的效率只與問題的規(guī)模有關，而與數據的存儲結構無關

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

C．數據的邏輯結構與存儲結構是一一對應的

D．算法的時間復雜度與空間復雜度一定相關

【答案】B

【解析】A項錯誤的，效率與存儲結構有密切關系。B項正確，算法的時間復雜度是指算法在計算機內執(zhí)行時所需時間的度量。C項錯誤，邏輯結構與存儲結構是兩個概念不可能一一對應的。D項錯誤，算法的時間復雜度與空間復雜度是獨立的。答案選擇B選項。

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

A．算法在執(zhí)行過程中所需要的計算機存儲空間

B．算法所處理的數據量

C．算法程序中的語句或指令條數

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

【答案】A

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

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

A．算法程序的長度

B．算法所處理的數據量

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

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

【答案】D

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