第1章 算法初步

1.1 什么是算法

1.1.1 算法的定義

對算法的解釋，從古至今定義是不唯一的。本書給出的算法的定義是：一系列用來解決單個或多個問題，或有執行計算功能的命令的集合。而聯系上輸入與輸出，算法就是將輸入轉換為輸出的一系列計算步驟的集合。生動地講，可以把一個程序比作一道菜。如圖1-1所示，做菜的原材料就是輸入，做出來的成品即為輸出；而算法，就是做菜過程中的復雜步驟。

算法的本質其實是數學的理論與推導。在還沒有發明求和公式之前，如何求出1+2+3+…+n？逐個數求和雖能算出答案，但終究過于繁雜，如果n=10000呢？但反觀求和公式，無論n取多大的值，計算的步驟和繁瑣程度基本不會增加。這就是算法存在的意義。人類在解決復雜問題時所采用的一系列特定的方法，即為算法。

1.1.2 算法與程序的區別

算法和程序的定義有很大交集。通常來說，（計算機）程序指一組計算機能識別和執行，并有一定功能的指令。后者的定義似乎和算法很相似，但兩者最大的區別在于程序是以計算機能夠理解的各式各樣的編程語言編寫而成的，而算法是可以通過編程語言、圖繪、口述等人能夠理解的方式來描述的，不一定局限于編程語言的詮釋，如圖1-2所示。不過，算法和程序之間并沒有明確的分界線，理解二者的意思就足夠了。

剛才曾提過，算法是一種以數學為本質的計算方法。然而作為方法，則必有正確（可行）、不正確（不可行），高效、低效之分。若一個算法對每一個恰當的輸入（嚴格地符合問題的前提條件，且可以為空）都以正確的輸出終止程序，則可以稱該算法是正確的，并正確地解決了給定的問題。若算法以不正確的輸出而終止程序，或根本無法終止程序（如程序陷入死循環），則這個算法是不正確的。

但顯而易見，不是所有的算法都可以通過輸入和輸出的正確和不正確而簡單地分為兩大類。譬如人們要預測未來特定事件發生概率，而這種問題無法用結果來檢驗解決方法正確與否。因此，算法的正確性的檢驗也可以回溯到其本質，就是數學的檢驗，也就是說用數學來證明算法的正確性或可行性。

對算法至關重要的不只有其正確性，還有它的效率。人類至今的發展，提高最迅速的可以說就是計算的效率了。從原始人的結繩計數，到現在的超級計算機，計算能力的提升不是區區幾個數量級能說明的。但很不幸，當今計算機的運算速度不是無限快，存儲器也不是免費的，所以如何高效地利用好有限的時間和空間就是算法存在的意義。有趣的是，求解相同問題而設計的不同算法在效率方面通常有顯著的差異，而這些算法效率上的差異要比在硬件或者軟件效率上的差異大得多。

回到1+2+3+…+n這個求和問題中。一定程度上說，逐個數相加也可以被看作一種解決求和問題的算法，一種簡單、低效的算法。相反，求和公式則是一種較復雜、高效的算法。但如何來評判一個算法是否高效？時間復雜度和空間復雜度就是很好的丈量工具。