1.3　算法概述

1.3.1　算法的概念

算法（Algorithm）是為解決一個問題采取的方法和步驟，也就是說，算法是為實現某種計算過程而規定的基本動作的執行序列。算法分兩大類：數值計算方法和非數值計算方法。

算法有如下特點：

（1）算法的操作步驟有限，即算法的有窮性（Finiteness），也就是算法要有的合理限度。算法執行步數存在上界，要在執行有限步驟后終止。所謂算法的合理限度，是指執行時間的合理限度，如果一個算法的執行時間超過了這一限度，盡管可行，但算法本身已無實用價值。

（2）算法的每一步驟都應為確定的，即算法的確定性（Definiteness）。也就是說，算法的每一步必須明確描述，在執行的過程中不能存在歧義性。對于每一種情況，需要執行的動作都應嚴格地、清晰地規定，不然計算機將無所適從。

（3）執行算法時可從外界輸入信息，即算法需要足夠的輸入信息（Information）。在算法開始執行時提供一組輸入數據，輸入數據的個數可以是0個或多個。算法中的各種輸入信息是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態。故一個算法的結果與其輸入的初始數據有關。提供的輸入信息不足時，算法可能是無效的。

（4）算法的目的是為了求解，因此算法要有輸出，即算法的輸出（Output）。執行算法可以有1個或多個輸出。如果一個算法無輸出，則該算法是無意義的。

（5）算法的每一步都應有效地執行，即算法的有效性（Effectiveness）。算法的每一步必須是能實現的，且應得到確定的結果，即最后得到結果或得到“不可解”的陳述。對于不同的輸入數據可以得到不同的結果，對于同一組輸入數據，應得到相同的、確定的結果，以達到預期的目的。從算法的具體執行過程來看，算法的執行步驟應該與計算機的指令集相符合，且要對應具體的指令集。超出計算機運算能力的算法步驟無法實現。

對于某一個特定問題的求解，究竟采用何種數據結構及選擇什么算法，需要對該問題進行分析。這要看問題的具體要求和現實環境的各種條件，然后把數據結構與算法有機地結合起來，才能設計出高質量的計算機程序。算法必須采用與之相適應的數據結構，才能有效地計算所求解的問題。

算法的含義與程序十分相似，但二者是有區別的。算法與程序不同，程序可以不滿足上述的特性。一個程序不一定滿足有窮性（可以是無限循環）。另外，程序中的指令必須是機器可執行的，而算法中的指令則無此限制。一個算法若用計算機語言來書寫，則它就可以是一個程序。

程序設計人員需要對程序要處理的問題準確理解，只有準確理解問題才能夠研究出解決問題的方法。對于任何實際問題，經過分析得到計算機能解決的數學模型，然后選擇數據結構組織數據，選擇算法進行計算。Wegner強調數據結構的重要性，認為計算機科學中具有核心作用的概念是“信息結構的轉換”。Knuth則強調算法的重要性，認為計算機科學是算法的學問，算法的特殊表示稱為“程序”。

隨著科學技術的發展，人們要求計算機處理和傳輸的信息量越來越大，結構也越來越復雜，對數據結構的研究要求越來越高，要求構造和使用各種數據結構。而任何一種類型的數據需要施加各種運算，必須通過算法實現，任何算法的選擇也要聯系著處理的對象和結果。也就是說，數據結構和算法之間有著本質的聯系。因此，算法與數據結構應該結合起來進行研究和分析，以達到使用計算機高效和可靠地處理數據的目的。