序章
算法的基本知識(shí)

0-1 什么是算法

算法與程序的區(qū)別

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

食譜和算法之間最大的區(qū)別就在于算法是嚴(yán)密的。食譜上經(jīng)常會(huì)有描述得比較模糊的部分，而算法的步驟都是用數(shù)學(xué)方式來(lái)描述的，所以十分明確。

算法和程序有些相似，區(qū)別在于程序是以計(jì)算機(jī)能夠理解的編程語(yǔ)言編寫(xiě)而成的，可以在計(jì)算機(jī)上運(yùn)行，而算法是以人類能夠理解的方式描述的，用于編寫(xiě)程序之前。不過(guò)，在這個(gè)過(guò)程中到哪里為止是算法、從哪里開(kāi)始是程序，并沒(méi)有明確的界限。

就算使用同一個(gè)算法，編程語(yǔ)言不同，寫(xiě)出來(lái)的程序也不同；即便使用相同的編程語(yǔ)言，寫(xiě)程序的人不同，那么寫(xiě)出來(lái)的程序也是不同的。

排列整數(shù)的算法：排序

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

來(lái)看一個(gè)具體的算法示例吧。這是一個(gè)以隨意排列的整數(shù)為輸入，把它們按從小到大的順序重新排列的問(wèn)題。這類排序問(wèn)題我們將在第2章詳細(xì)講解。

只解決這一個(gè)問(wèn)題很簡(jiǎn)單，但是算法是可以應(yīng)對(duì)任意輸入的計(jì)算步驟，所以必須采用通用的描述。雖然在這個(gè)示例中輸入的整數(shù)個(gè)數(shù)n為8，然而不管n多大，算法都必須將問(wèn)題解決。

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

這之后1的位置便固定下來(lái)，不再移動(dòng)。接下來(lái)，在剩下的數(shù)字里繼續(xù)尋找最小數(shù)，再將它和左邊第2個(gè)數(shù)字交換位置。于是，4和13也交換了位置。

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

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

?用計(jì)算機(jī)能理解的方式構(gòu)思解法：算法的設(shè)計(jì)

計(jì)算機(jī)擅長(zhǎng)高速執(zhí)行一些基本命令，但無(wú)法執(zhí)行復(fù)雜的命令。此處的“基本命令”指的是“做加法”或者“在指定的內(nèi)存地址上保存數(shù)據(jù)”等。

計(jì)算機(jī)是以這些基本命令的組合為基礎(chǔ)運(yùn)行的，面對(duì)復(fù)雜的操作，也是通過(guò)搭配組合這些基本命令來(lái)應(yīng)對(duì)的。上文中提到的“對(duì)n個(gè)數(shù)字進(jìn)行排序”對(duì)計(jì)算機(jī)來(lái)說(shuō)就是復(fù)雜的操作。如何設(shè)計(jì)算法來(lái)解決這個(gè)排序問(wèn)題，也就等同于構(gòu)思如何搭配組合計(jì)算機(jī)可以執(zhí)行的那些基本命令來(lái)實(shí)現(xiàn)這個(gè)操作。

如何選擇算法

能解決排序問(wèn)題的算法不止選擇排序這一個(gè)。那么，當(dāng)有多個(gè)算法都可以解決同一個(gè)問(wèn)題時(shí)，我們?cè)撊绾芜x擇呢？在算法的評(píng)判上，考量的標(biāo)準(zhǔn)也各有不同。

比如，簡(jiǎn)單的算法對(duì)人來(lái)說(shuō)易于理解，也容易被寫(xiě)成程序，而在運(yùn)行過(guò)程中不需要耗費(fèi)太多空間資源的算法，就十分適用于內(nèi)存小的計(jì)算機(jī)。

不過(guò)，一般來(lái)說(shuō)我們最為重視的是算法的運(yùn)行時(shí)間，即從輸入數(shù)據(jù)到輸出結(jié)果這個(gè)過(guò)程所花費(fèi)的時(shí)間。

對(duì)50個(gè)數(shù)字排序所花的時(shí)間竟然比宇宙的歷史還要長(zhǎng)嗎

?使用全排列算法進(jìn)行排序

為了讓大家體會(huì)一下低效率算法的效果，這里來(lái)看看下面這個(gè)排序算法。

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

那么，需要等多久才能出結(jié)果呢？若運(yùn)氣好，很快就能出現(xiàn)正確排列的話，結(jié)果也就立馬出來(lái)了。然而，實(shí)際情況往往并不如我們所愿。最差的情況，也就是直到最后才出現(xiàn)正確排列的情況下，計(jì)算機(jī)就不得不確認(rèn)所有可能的排列了。

n個(gè)數(shù)字有n！種不同的排列方法（n! =n（n-1）（n-2）…3·2·1）。現(xiàn)在，我們來(lái)看看n=50時(shí)是怎樣一種情況吧。

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

假設(shè)1臺(tái)高性能計(jì)算機(jī)1秒能檢查1萬(wàn)億（=1012）個(gè)數(shù)列，那么檢查1040個(gè)數(shù)列將花費(fèi)的時(shí)間為1040÷1012=1028秒。1年為31536000秒，不到108秒。因此，1028秒＞1020年。

從大爆炸開(kāi)始宇宙已經(jīng)經(jīng)歷了約137億年，即便如此也少于1011年。也就是說(shuō)，僅僅是對(duì)50個(gè)數(shù)字進(jìn)行排序，若使用全排列算法，就算花費(fèi)宇宙年齡的109倍時(shí)間也得不出答案。

?使用選擇排序算法進(jìn)行排序

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

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

n=50的時(shí)候n2=2500。假設(shè)1秒能確認(rèn)1萬(wàn)億（=1012）個(gè)數(shù)字，那么2500÷1012=0.0000000025秒便能得出結(jié)果，比全排列算法的效率高得多。