序章
算法的基本知識

0-1 什么是算法

算法與程序的區別

算法就是計算或者解決問題的步驟。我們可以把它想象成食譜。要想做出特定的料理，就要遵循食譜上的步驟；同理，要想用計算機解決特定的問題，就要遵循算法。這里所說的特定問題多種多樣，比如“將隨意排列的數字按從小到大的順序重新排列”“尋找出發點到目的地的最短路徑”，等等。

食譜和算法之間最大的區別就在于算法是嚴密的。食譜上經常會有描述得比較模糊的部分，而算法的步驟都是用數學方式來描述的，所以十分明確。

算法和程序有些相似，區別在于程序是以計算機能夠理解的編程語言編寫而成的，可以在計算機上運行，而算法是以人類能夠理解的方式描述的，用于編寫程序之前。不過，在這個過程中到哪里為止是算法、從哪里開始是程序，并沒有明確的界限。

就算使用同一個算法，編程語言不同，寫出來的程序也不同；即便使用相同的編程語言，寫程序的人不同，那么寫出來的程序也是不同的。

排列整數的算法：排序

?查找最小的數字并交換：選擇排序

來看一個具體的算法示例吧。這是一個以隨意排列的整數為輸入，把它們按從小到大的順序重新排列的問題。這類排序問題我們將在第2章詳細講解。

只解決這一個問題很簡單，但是算法是可以應對任意輸入的計算步驟，所以必須采用通用的描述。雖然在這個示例中輸入的整數個數n為8，然而不管n多大，算法都必須將問題解決。

那么，你首先想到的方法，是不是先從輸入的數字中找出最小的數字，再將它和最左邊的數字交換位置呢？在這個示例中就是找到最小數字1，然后將它和最左邊的7交換位置。

這之后1的位置便固定下來，不再移動。接下來，在剩下的數字里繼續尋找最小數，再將它和左邊第2個數字交換位置。于是，4和13也交換了位置。

我們將這樣的一次交換稱為“1輪”。到了第k輪的時候，就把剩下的數字中最小的一個，與左邊開始第k個數字進行交換。于是在結束第k輪后，從左數的k個數字便都按從小到大的順序排列了。只要將這個步驟重復n次，那么所有的數字都將按從小到大的順序排列。

這便是我們將在2-3節中介紹的選擇排序。不管輸入的數字是什么、n有多大，都可以用這個算法解決問題。

?用計算機能理解的方式構思解法：算法的設計

計算機擅長高速執行一些基本命令，但無法執行復雜的命令。此處的“基本命令”指的是“做加法”或者“在指定的內存地址上保存數據”等。

計算機是以這些基本命令的組合為基礎運行的，面對復雜的操作，也是通過搭配組合這些基本命令來應對的。上文中提到的“對n個數字進行排序”對計算機來說就是復雜的操作。如何設計算法來解決這個排序問題，也就等同于構思如何搭配組合計算機可以執行的那些基本命令來實現這個操作。

如何選擇算法

能解決排序問題的算法不止選擇排序這一個。那么，當有多個算法都可以解決同一個問題時，我們該如何選擇呢？在算法的評判上，考量的標準也各有不同。

比如，簡單的算法對人來說易于理解，也容易被寫成程序，而在運行過程中不需要耗費太多空間資源的算法，就十分適用于內存小的計算機。

不過，一般來說我們最為重視的是算法的運行時間，即從輸入數據到輸出結果這個過程所花費的時間。

對50個數字排序所花的時間竟然比宇宙的歷史還要長嗎

?使用全排列算法進行排序

為了讓大家體會一下低效率算法的效果，這里來看看下面這個排序算法。

我們就把這個算法稱為“全排列算法”吧。全排列算法列出了所有的排列方法，所以不管輸入如何，都可以得到正確的結果。

那么，需要等多久才能出結果呢？若運氣好，很快就能出現正確排列的話，結果也就立馬出來了。然而，實際情況往往并不如我們所愿。最差的情況，也就是直到最后才出現正確排列的情況下，計算機就不得不確認所有可能的排列了。

n個數字有n！種不同的排列方法（n! =n（n-1）（n-2）…3·2·1）。現在，我們來看看n=50時是怎樣一種情況吧。

公式①中，50！即為數字1到數字50的乘積。為了便于計算，我們通過公式②③將結果近似轉換為10的n次方的形式。公式②右邊部分去掉了10以下的數字，因此小于50!。公式③左右都是40個數字的乘積，但左邊數字都大于10，因此大于右邊的1040。接下來我們就用1040近似代表50個數字的所有排列情況來進行計算。

假設1臺高性能計算機1秒能檢查1萬億（=1012）個數列，那么檢查1040個數列將花費的時間為1040÷1012=1028秒。1年為31536000秒，不到108秒。因此，1028秒＞1020年。

從大爆炸開始宇宙已經經歷了約137億年，即便如此也少于1011年。也就是說，僅僅是對50個數字進行排序，若使用全排列算法，就算花費宇宙年齡的109倍時間也得不出答案。

?使用選擇排序算法進行排序

那么，使用前文提到的選擇排序算法，情況又將如何呢？

首先，為了在第1輪找到最小的數字，需要從左往右確認數列中的數字，只要查詢n個數字即可。在接下來的第2輪中，需要從n-1個數字中尋找最小值，所以需要查詢n-1個數字。將這個步驟進行到第n輪的時候，需要查詢的次數如下。

n=50的時候n2=2500。假設1秒能確認1萬億（=1012）個數字，那么2500÷1012=0.0000000025秒便能得出結果，比全排列算法的效率高得多。