我的第一本演算法書

1

演算法與程序的區別

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

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

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

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

排列整數的演算法：排序

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

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

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

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

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

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

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

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

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

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

2

如何選擇演算法

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

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

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

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

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

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

生成一個由個數字構成的數列（不和前面生成的數列重複）

如果中生成的數列按從小到大的順序排列就將其輸出，否則回到步驟

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

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

個數字有種不同的排列方法。現在，我們來看看時是怎樣一種情況吧。

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

假設 1 台高性能計算機 1 秒能檢查 1 萬億（）個數列，那麼檢查個數列將花費的時間為秒。1 年為 31 536 000 秒，不到秒。因此，秒＞年。

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

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

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

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

的時候。假設 1 秒能確認 1 萬億（）個數字，那麼秒便能得出結果，比全排列演算法的效率高得多。

No. 0-2　運行時間的計算方法

了解輸入數據的量和運行時間之間的關係

上一節在結尾說明了演算法的不同會導致其運行時間產生大幅變化，本節將講解如何求得演算法的運行時間。

使用相同的演算法，輸入數據的量不同，運行時間也會不同。比如，對 10 個數字排序和對 1 000 000 個數字排序，大家很容易就想到後者的運行時間更長。那麼，實際上運行時間會長多少呢？後者是前者的 100 倍，還是 1 000 000 倍？就像這樣，我們不光要理解不同演算法在運行時間上的區別，還要了解根據輸入數據量的大小，演算法的運行時間具體會產生多大的變化。

3

如何求得運行時間

那麼，如何測算不同輸入所導致的運行時間的變化程度呢？最為現實的方法就是在計算機上運行一下程序，測試其實際花費的時間。但是，就算使用同樣的演算法，花費的時間也會根據所用計算機的不同而產生偏差，十分不便。

所以在這裡，我們使用「步數」來描述運行時間。「1 步」就是計算的基本單位。通過測試「計算從開始到結束總共執行了多少步」來求得演算法的運行時間。

作為示例，現在我們試著從理論層面求出選擇排序的運行時間。選擇排序的步驟如下。

從數列中尋找最小值

將最小值和數列最左邊的數字進行交換，排序結束。回到

如果數列中有個數字，那麼中「尋找最小值」的步驟只需確認個數字即可。這裡，將「確認 1 個數字的大小」作為操作的基本單位，需要的時間設為，那麼步驟的運行時間就是。

接下來，把「對兩個數字進行交換」也作為操作的基本單位，需要的時間設為。那麼，和總共重複次，每經過「1 輪」，需要查找的數字就減少 1 個，因此總的運行時間如下。

雖說只剩最後 1 個數字的時候就不需要確認了，但是方便起見還是把對它的確認和交換時間計算在內比較好。

4

運行時間的表示方法

雖說我們已經求得了運行時間，但其實這個結果還可以簡化。和都是基本單位，與輸入無關。會根據輸入變化而變化的只有數列的長度，所以接下來考慮變大的情況。越大，上式中的也就越大，其他部分就相對變小了。也就是說，對式子影響最大的是。所以，我們刪掉其他部分，將結果表示成下式右邊的形式。

通過這種表示方法，我們就能大致了解到排序演算法的運行時間與輸入數據量的平方成正比。同樣地，假設某個演算法的運行時間如下。

那麼，這個結果就可以用來表示。如果運行時間為

這個結果就可以用來表示。

這個符號的意思是「忽略重要項以外的內容」，讀音同 Order。的含義就是「演算法的運行時間最長也就是的常數倍」，準確的定義請參考相關專業書籍。重點在於，通過這種表示方法，我們可以直觀地了解演算法的時間複雜度 1。

1時間複雜度是一個可以描述演算法運行時間的函數，常用大符號來表述。——譯者注

比如，當我們知道選擇排序的時間複雜度為、快速排序的時間複雜度為時，很快就能判斷出快速排序的運算更為高速。二者的運行時間根據輸入產生的變化程度也一目了然。

關於演算法的基本知識就介紹到這裡了。從下一章開始，我們就來具體學習各種演算法吧。

本文來自《我的第一本演算法書》

作者：石田保輝

碼書商店是CSDN專為我們的用戶建立的一個商店，這裡提供大量的技術書籍，除了書籍我們也提供生活類的相關產品，如耳機、鍵盤等，或者你們如果有需求也可以聯繫碼書商店的客服或者在公眾號下留言你們需要的產品，我們盡量滿足大家需求哦。

作為碼書商店的運營人員，誠邀你們進入我們的「CSDN碼書福利群」，群里會不定時的給大家贈書書籍、優惠券等，有書籍推薦或者物流方面信息也可群里諮詢~目前群已滿100人，需要加群的請掃下方二維碼添加微信，拉你入群哦~

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！