演算法與程序的區別

懂一點計算機知識

是現代人必備的素養

否則人生就是有缺憾的

以下文章選自

《我的第一本演算法書》

作者：【日】石田保輝

圖靈教育書系

以通俗易懂的圖文方式

為你掃盲演算法

內容提要

本書採用大量圖片，通過詳細的分步講解，以直觀、易懂的方式展現了7個數據結構和26個基礎演算法的基本原理。第1章介紹了鏈表、數組、棧等7個數據結構；從第2章到第7章，分別介紹了和排序、查找、圖論、安全、聚類等相關的26個基礎演算法，內容涉及冒泡排序、二分查找、廣度優先搜索、哈希函數、迪菲 - 赫爾曼密鑰交換、k-means 演算法等。 本書沒有枯燥的理論和複雜的公式，而是通過大量的步驟圖幫助讀者加深對數據結構原理和演算法執行過程的理解，便於學習和記憶。將本書作為演算法入門的第一步，是非常不錯的選擇。

演算法的基本知識

演算法與程序的區別

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

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

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

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

排列整數的演算法：排序

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

來看一個具體的演算法示例吧。這是一個以隨意排列的整數為輸入，把它們按從小到大的順序重新排列的問題。這類排序問題我們將在第 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(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 年為 31 536 000 秒，不到 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.000 000 002 5秒便能得出結果，比全排列演算法的效率高得多。

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

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

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

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

如何求得運行時間

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

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

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

從數列中尋找最小值

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

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

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

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

運行時間的表示方法

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

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

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

這個結果就可以用 O(nlogn) 來表示。

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

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

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

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

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