1.1　建立算法初步概念

很多開發者都知道“程序=數據結構+算法”這個著名的公式，但卻并不真正明白算法的定義或者概念。

1.1.1　什么是算法

究竟什么是算法（algorithm）呢？從字面意義上理解，算法即用于計算的方法，通過這種方法可以達到預期的計算結果。

此外，在一般的教科書或者字典中也有關于算法的專業解釋，例如，算法是解決實際問題的一種精確描述方法、算法是對特定問題的求解步驟的一種精確描述方法等。目前，被廣泛認可的算法的專業定義是，算法是模型分析的一組可行的、確定的和有窮的規則。

其實，通俗地講，算法可以理解為一個完整的解題步驟，由一些基本運算和規定的運算順序構成。通過這樣的解題步驟可以解決特定的問題。從計算機程序設計的角度看，算法由一系列求解問題的指令構成，能夠根據規范的輸入，在有限的時間內獲得有效的輸出結果。算法代表了用系統的方法來描述解決問題的一種策略機制。

舉一個例子來分析算法是如何在現實生活中發揮作用的。最典型的例子就是統籌安排，假設有3件事（事件A、事件B和事件C）要做：

?做事件A需要耗費5分鐘；

?做事件B需要耗費5分鐘但需要15分鐘的時間才可以得到結果，如燒水等待水開的過程；

?做事件C需要耗費10分鐘。

那么應該怎樣來做這三件事情呢？一種方法是依次做，如圖1-1所示，做完事件A，再做事情B，最后做事情C。這樣，總的耗時為5+（5+15）+10=35分鐘，這顯然是浪費時間的一種方法。

在實際生活中比較可取的方法是，先做事件B，在等待事件B完成的過程中做事件A和事件C。這樣，等待事件B完成的15分鐘正好可以完成事件A和事件C。此時，總的耗時為5+15=20分鐘，效率明顯提高，如圖1-2所示。

在上述例子中提到的兩種方法就可以看作兩種算法。第一種算法效率低，第二種算法效率高，但都達到了做完事情的目的。從這個例子可以看出，算法也是有好壞區別的，好的算法可以提高工作的效率。算法的基本任務是針對一個具體的問題，找到一個高效的處理方法，從而獲得最佳的結果。

一個典型的算法一般都可以從中抽象出5個特征：有窮性、確切性、輸入、輸出和可行性。下面結合上述例子來分析這5個特征。

?有窮性：算法的指令或者步驟的執行次數是有限的，執行時間也是有限的。例如，在上面的例子中，通過短短的幾步就可以完成任務，而且執行時間都是有限的。

?確切性：算法的每一個指令或者步驟都必須有明確的定義和描述。例如，在上面的例子中，為了完成三件事情的任務，每一步做什么事情都有明確的規定。

?輸入：一個算法應該有相應的輸入條件，用來刻畫運算對象的初始情況。例如，在上面的例子中，有三個待完成的事件（事件A、事件B和事件C），這三個事件便是輸入。

?輸出：一個算法應該有明確的結果輸出。這是容易理解的，因為沒有得到結果的算法毫無意義。例如，在上面的例子中，輸出結果便是三件事情全部做完了。

?可行性：算法的執行步驟必須是可行的，且可以在有限時間內完成。例如，在上面的例子中，每一個步驟都切實可行。其實，無法執行的步驟也是毫無意義的，解決不了任何實際問題。

目前，算法的應用非常廣泛，常用的算法包括遞推算法、遞歸算法、窮舉算法、貪婪算法、分治算法、動態規劃算法和迭代算法等多種。本書將逐步向讀者展示各種算法的原理和應用。

1.1.2　算法的發展歷史

關于算法的起源，可以追溯到我國古代公元前1世紀的《周髀算經》，它是算經的十書之一，原名《周髀》，主要闡述古代中國的蓋天說和四分歷法。在唐朝的時候，此書被定為國子監明算科的教材之一，并改名為《周髀算經》。算法在我國古代稱為“演算法”。《周髀算經》中記載了勾股定理、開平方問題、等差級數問題等，其中用到了相當復雜的分數算法和開平方算法等。在隨后的發展中，出現了割圓術、秦九韶算法和剩余定理等一些經典算法。

在西方，公元9世紀波斯數學家al-Khwarizmi提出了算法的概念。“算法”最初寫為algorism，意思是采用阿拉伯數字的運算法則。到了18世紀，算法正式命名為algorithm。由于漢字計算的不方便，導致我國古代算法的發展比較緩慢，而采用阿拉伯數字的西方國家則發展迅速。例如，著名的歐幾里德算法（又稱輾轉相除法）就是典型的算法。

在歷史上，Ada Byron被認為是第一個程序員。她在1842年編寫的巴貝奇分析機上的伯努利方程的求解算法程序雖然未能執行，但奠定了計算機算法程序設計的基礎。

后來，隨著計算機的發展，在計算機中實現各種算法已成為可能。算法在計算機程序設計領域又得到了重要發展。目前，幾乎所有的程序員編程時，無論采用何種編程語言，都需要與算法打交道。

1.1.3　算法的分類

算法是一門古老且龐大的學科，隨著歷史的發展，演化出多種多樣的算法。按照不同的應用和特性，算法可以分為不同的類別。

1）按照應用來分類

按照算法的應用領域，即解決的問題，算法可以分為基本算法、數據結構相關的算法、幾何算法、圖論算法、規劃算法、數值分析算法、加密/解密算法、排序算法、查找算法、并行算法和數論算法等。

2）按照確定性來分類

按照算法結果的確定性來分類，算法可以分為確定性算法和非確定性算法。

?確定性算法：這類算法在有限的時間內完成計算，得到的結果是唯一的，且經常取決于輸入值。

?非確定性算法：這類算法在有限的時間內完成計算，但是得到的結果往往不是唯一的，即存在多值性。

3）按照算法的思路來分類

按照算法的思路來分類，算法可以分為遞推算法、遞歸算法、窮舉算法、貪婪算法、分治算法、動態規劃算法和迭代算法等多種算法。