算法:解題方案的準确而完整的描述-中文百科頻道

特征

一個算法應該具有以下五個重要的特征：

有窮性

（Finiteness）

算法的有窮性是指算法必須能在執行有限個步驟之後終止；

确切性

(Definiteness)

算法的每一步驟必須有确切的定義；

輸入項

(Input)

一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；

輸出項

(Output)

一個算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的算法是毫無意義的；

可行性

(Effectiveness)

算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步驟，即每個計算步驟都可以在有限時間内完成（也稱之為有效性）。

要素

一、數據對象的運算和操作：計算機可以執行的基本操作是以指令的形式描述的。一個計算機系統能執行的所有指令的集合，成為該計算機系統的指令系統。一個計算機的基本運算和操作有如下四類：

1.算術運算：加減乘除等運算

2.邏輯運算：或、且、非等運算

3.關系運算：大于、小于、等于、不等于等運算

4.數據傳輸：輸入、輸出、賦值等運算

二、算法的控制結構：一個算法的功能結構不僅取決于所選用的操作，而且還與各操作之間的執行順序有關。

評定

同一問題可用不同算法解決，而一個算法的質量優劣将影響到算法乃至程序的效率。算法分析的目的在于選擇合适算法和改進算法。一個算法的評價主要從時間複雜度和空間複雜度來考慮。

時間複雜度

算法的時間複雜度是指執行算法所需要的計算工作量。一般來說，計算機算法是問題規模的函數，算法的時間複雜度也因此記做：

因此，問題的規模越大，算法執行的時間的增長率與的增長率正相關，稱作漸進時間複雜度（Asymptotic Time Complexity）。

空間複雜度

算法的空間複雜度是指算法需要消耗的内存空間。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。

正确性

算法的正确性是評價一個算法優劣的最重要的标準。

可讀性

算法的可讀性是指一個算法可供人們閱讀的容易程度。

魯棒性

魯棒性是指一個算法對不合理數據輸入的反應能力和處理能力，也稱為容錯性。

方法

遞推法

遞推是序列計算機中的一種常用算法。它是按照一定的規律來計算序列中的每個項，通常是通過計算機前面的一些項來得出序列中的指定項的值。其思想是把一個複雜的龐大的計算過程轉化為簡單過程的多次重複，該算法利用了計算機速度快和不知疲倦的機器特點。

遞歸法

程序調用自身的編程技巧稱為遞歸（recursion）。一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略隻需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

注意：

(1) 遞歸就是在過程或函數裡調用自身;

(2) 在使用遞歸策略時，必須有一個明确的遞歸結束條件，稱為遞歸出口。

窮舉法

窮舉法，或稱為暴力破解法，其基本思路是：對于要解決的問題，列舉出它的所有可能的情況，逐個判斷有哪些是符合問題所要求的條件，從而得到問題的解。它也常用于對于密碼的破譯，即将密碼進行逐個推算直到找出真正的密碼為止。例如一個已知是四位并且全部由數字組成的密碼，其可能共有10000種組合，因此最多嘗試10000次就能找到正确的密碼。理論上利用這種方法可以破解任何一種密碼，問題隻在于如何縮短試誤時間。因此有些人運用計算機來增加效率，有些人輔以字典來縮小密碼組合的範圍。

貪心算法

貪心算法是一種對某些求最優解問題的更簡單、更迅速的設計技術。

用貪心法設計算法的特點是一步一步地進行，常以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間，它采用自頂向下,以叠代的方法做出相繼的貪心選擇,每做一次貪心選擇就将所求問題簡化為一個規模更小的子問題, 通過每一步貪心選擇,可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此産生的全局解有時不一定是最優的，所以貪婪法不要回溯。

貪婪算法是一種改進了的分級處理方法，其核心是根據題意選取一種量度标準，然後将這多個輸入排成這種量度标準所要求的順序，按這種順序一次輸入一個量，如果這個輸入和當前已構成在這種量度意義下的部分最佳解加在一起不能産生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪算法。

對于一個給定的問題，往往可能有好幾種量度标準。初看起來，這些量度标準似乎都是可取的，但實際上，用其中的大多數量度标準作貪婪處理所得到該量度意義下的最優解并不是問題的最優解，而是次優解。因此，選擇能産生問題最優解的最優量度标準是使用貪婪算法的核心。

一般情況下，要選出最優量度标準并不是一件容易的事，但對某問題能選擇出最優量度标準後，用貪婪算法求解則特别有效。

分治法

分治法是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

分治法所能解決的問題一般具有以下幾個特征：

(1) 該問題的規模縮小到一定的程度就可以容易地解決；

(2) 該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質；

(3) 利用該問題分解出的子問題的解可以合并為該問題的解；

(4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

動态規劃法

動态規劃是一種在數學和計算機科學中使用的，用于求解包含重疊子問題的最優化問題的方法。其基本思想是，将原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動态規劃的思想是多種算法的基礎，被廣泛應用于計算機科學和工程領域。

動态規劃程序設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊算法。不像前面所述的那些搜索或數值計算那樣，具有一個标準的數學表達式和明确清晰的解題方法。動态規劃程序設計往往是針對一種最優化問題，由于各種問題的性質不同，确定最優解的條件也互不相同，因而動态規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動态規劃算法，可以解決各類最優化問題。因此讀者在學習時，除了要對基本概念和方法正确理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。

叠代法

叠代法也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程，跟叠代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。叠代法又分為精确叠代和近似叠代。“二分法”和“牛頓叠代法”屬于近似叠代法。叠代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、适合做重複性操作的特點，讓計算機對一組指令（或一定步驟）進行重複執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。

分支界限法

分枝界限法是一個用途十分廣泛的算法，運用這種算法的技巧性很強，不同類型的問題解法也各不相同。

分支定界法的基本思想是對有約束條件的最優化問題的所有可行解（數目有限）空間進行搜索。該算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），并為每個子集内的解的值計算一個下界或上界（稱為定界）。在每次分支後，對凡是界限超出已知可行解值那些子集不再做進一步分支，這樣，解的許多子集（即搜索樹上的許多結點）就可以不予考慮了，從而縮小了搜索範圍。這一過程一直進行到找出可行解為止，該可行解的值不大于任何子集的界限。因此這種算法一般可以求得最優解。

與貪心算法一樣，這種方法也是用來為組合優化問題設計求解算法的，所不同的是它在問題的整個可能解空間搜索，所設計出來的算法雖其時間複雜度比貪婪算法高，但它的優點是與窮舉法類似，都能保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過程中通過限界，可以中途停止對某些不可能得到最優解的子空間進一步搜索（類似于人工智能中的剪枝），故它比窮舉法效率更高。

回溯法

回溯法（探索與回溯法）是一種選優搜索法，按選優條件向前搜索，以達到目标。但當探索到某一步時，發現原先選擇并不優或達不到目标，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀态的點稱為“回溯點”。

其基本思想是，在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隐式圖的深度優先搜索算法）。若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。而若使用回溯法求任一個解時，隻要搜索到問題的一個解就可以結束。

描述方式

描述算法的方法有多種，常用的有自然語言、結構化流程圖、僞代碼和PAD圖等，其中最普遍的是流程圖，分思法。

分類

算法可大緻分為基本算法、數據結構的算法、數論與代數算法、計算幾何的算法、圖論的算法、動态規劃以及數值分析、加密算法、排序算法、檢索算法、随機化算法、并行算法，厄米變形模型，随機森林算法。

算法可以宏泛的分為三類：

一、有限的，确定性算法這類算法在有限的一段時間内終止。他們可能要花很長時間來執行指定的任務，但仍将在一定的時間内終止。這類算法得出的結果常取決于輸入值。

二、有限的，非确定算法這類算法在有限的時間内終止。然而，對于一個（或一些）給定的數值，算法的結果并不是唯一的或确定的。

三、無限的算法是那些由于沒有定義終止定義條件，或定義的條件無法由輸入的數據滿足而不終止運行的算法。通常，無限算法的産生是由于未能确定的定義終止條件。

曆史

“算法”即演算法的大陸中文名稱出自《周髀算經》；而英文名稱Algorithm 來自于9世紀波斯數學家al-Khwarizmi，因為al-Khwarizmi在數學上提出了算法這個概念。“算法”原為"algorism"，意思是阿拉伯數字的運算法則，在18世紀演變為"algorithm"。歐幾裡得算法被人們認為是史上第一個算法。第一次編寫程序是Ada Byron于1842年為巴貝奇分析機編寫求解伯努利方程的程序，因此Ada Byron被大多數人認為是世界上第一位程序員。因為查爾斯·巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機，這個算法未能在巴貝奇分析機上執行。因為"well-defined procedure"缺少數學上精确的定義，19世紀和20世紀早期的數學家、邏輯學家在定義算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了算法定義的難題，圖靈的思想對算法的發展起到了重要作用。