1.1　算　法

視頻二維碼（掃碼觀看）

一、算法的基本概念

1算法的定義

算法是指解題方案的準確而完整的描述，即算法是對特定問題求解步驟的一種描述。

【注意】算法不等于程序，也不等于計算方法。

2算法的基本特征

（1）可行性（Effectiveness）：算法中的每一個步驟必須能夠實現，執行的結果要能夠達到預期的目的。

（2）確定性（Definiteness）：算法中的每一個步驟都必須是有明確定義的，不允許有模棱兩可的解釋或多義性。

（3）有窮性（Finiteness）：算法必須能在有限的時間（合理的時間）內做完，即算法必須能在執行有限個步驟之后終止。

（4）擁有足夠的情報：輸入是否足夠并正確，輸出是否合理。初始狀態是否正確。

二、算法設計基本方法

1列舉法

（1）基本思想

根據提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。

（2）特點

簡單，方便用計算機進行大量列舉；情況較多時，工作量將會很大。

（3）使用

將與問題有關的知識條理化、完備化、系統化，從中找出規律，進行分類，減少列舉量。

【例1】今有雞母一，值錢三；雞翁一，值錢二；雞雛一，值錢半。凡百錢買百雞，問雞母、雞翁、雞雛各幾何？

假設買母雞I只、公雞J只、小雞K只。根據題意，粗略的列舉算法描述如下：

共有三層循環，每層循環各需要循環101次，大約為100萬次。

優化后的算法

共有兩層循環，循環次數為

2歸納法

（1）基本思想

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

（2）特點

歸納是一種抽象，即從特殊現象中找出一般關系。

（3）使用

由于在歸納的過程中不可能對所有的情況進行列舉。因此，最后由歸納得到的結論還只是一種猜測，還需要對這種猜測加以必要的證明。實際上，通過精心觀察而得到的猜測得不到證實或最后證明猜測是錯的，也是常有的事。

3遞推

（1）基本思想

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

（2）特點

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

（3）使用

遞推算法在數值計算中是極為常見的。但是，對于數值型的遞推算法必須要注意數值計算的穩定性問題。

4遞歸

（1）基本思想

為了降低問題的復雜程度，將問題逐層分解，最后歸結為一些最簡單的問題，這種將問題逐層分解的過程，實際上并沒有對問題進行求解，而只是當解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合。

（2）特點

結構清晰，可讀性強。

（3）使用

遞歸在可計算性理論和算法設計中占有很重要的地位。

（4）分類

直接遞歸（自己調用自己）和間接遞歸（P調用Q，Q又調用P）。

【例2】編寫一個過程，對于輸入的參數n，依次打印輸出自然數1到n。

非遞歸算法：

遞歸算法：

5減半遞推技術

所謂“減半”，是指將問題的規模減半，而問題的性質不變；所謂“遞推”，是指重復“減半”的過程。

【例3】設方程f（x）＝0在區間[a，b]上有實根，且f（a）與f（b）異號。利用二分法求該方程在區間[a，b]上的一個實根。

用二分法求方程實根的減半遞推過程如下：

（1）首先取給定區間的中點c＝（a＋b）/2。

（2）然后判斷f（c）是否為0：

如果f（c）＝0，則說明c即為所求的根，求解過程結束；

如果f（c）≠0，則根據以下原則將原區間減半：

①若f（a）f（c）＜0，則取原區間的前半部分；

②若f（b）f（c）＜0，則取原區間的后半部分。

（3）最后判斷減半后的區間長度是否已經很小：

①若|a－b|＜ε，則過程結束，取（a＋b）/2為根的近似值；

②若|a－b|≥ε，則重復上述的減半過程。

6回溯法

（1）基本思想

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

（2）特點

在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進行無限的列舉。對于這類問題，一種有效的方法是“試”。

三、算法復雜度

主要包括時間復雜度和空間復雜度。

1算法的時間復雜度

（1）定義

執行算法所需要的計算工作量。

（2）衡量標準

通常用算法在執行過程中所需基本運算的執行次數來度量算法的工作量。算法所執行的基本運算次數還與問題的規模有關。

綜上所述，算法的工作量用算法所執行的基本運算次數來度量，而算法所執行的基本運算次數是問題規模的函數，即算法的工作量＝f（n）。

（3）存在問題

算法所執行的基本運算次數還可能與特定的輸入有關，而實際上又不可能將所有可能情況下算法所執行的基本運算次數都列舉出來。

（4）解決方法

①平均性態（Average Behavior）

用各種特定輸入下的基本運算次數的加權平均值來度量算法的工作量：

②最壞情況復雜性（Worst-Case Complexity）

規模為n時，算法所執行的基本運算的最大次數：

2算法的空間復雜度

【定義】執行這個算法所需要的內存空間。

（1）算法程序所占的空間；

（2）輸入的初始數據所占的存儲空間；

（3）算法執行過程中所需要的額外空間。

【注意】

①如果額外空間量相對于問題規模來說是常數，則稱該算法是原地工作的。

②在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術，以便盡量減少不必要的額外空間。

【考題1】算法的時間復雜度是指（　　）。

A．執行算法程序所需要的時間

B．算法程序的長度

C．算法執行過程中所需要的基本運算次數

D．算法執行過程中所需要的所有運算次數

E．算法程序中的指令條數

【答案】C

【解析】算法的時間復雜度是指算法執行過程中所需要的基本運算次數。執行算法程序所需要的時間、算法長度、指令條數等與時間復雜度沒有直接關系。

【考題2】算法的空間復雜度是指（　　）。

A．算法程序的長度

B．算法程序中的指令條數

C．算法程序所占的存儲空間

D．算法執行過程中所需要的存儲空間

E．算法所處理的數據量

【答案】D

【解析】算法的空間復雜度是指算法執行過程中所需要的存儲空間。算法程序的長度、指令條數、所處理的數據量等與空間復雜度沒有直接關系。