為什麼要學習算法？

算法是什麼？可能大多數讀者都不能準確地給算法下一個定義。其實在日常生活中，我們已經在無意中接觸過算法，通過本文，讓我們更加深入地領略算法的奧妙！

我們首先介紹算法的基本概念以及它的重要性。接著，我們通過兩個整數相乘的問題來說明精妙的算法是怎樣改進那些簡單或粗糙的解決方案的。然後，我們詳細討論了歸併排序算法。之所以選擇這個算法是出於下面這些理由：首先，它是一種非常實用並且非常有名的算法，是讀者應該掌握的；其次，它是一種非常合適的“熱身”算法，可以為以後學習更復雜的算法打下良好的基礎；最後，它是分治算法設計範式的權威引導教程。在本文的最後，我們將描述並使用算法分析的指導原則對本文所介紹的算法進行分析。

為什麼要學習算法

我們首先要闡明本文的價值，幫助讀者激發學習算法的熱情。那麼，什麼是算法呢？它是一組具有良好定義的規則（或者說是一種配方），可以有效地解決一些計算方面的問題。我們可能要處理一大串數字，需要對它們進行重新整理，使它們按順序排列；我們可能需要在地圖上計算從某個起點到某個目標地點的最短路徑；我們可能需要在某個最後期限之前完成一些任務，並且需要知道應該按照什麼樣的順序完成這些任務，使它們都能在各自的最後期限之前完成。

我們為什麼要學習算法呢？

算法對計算機科學的所有分支都非常重要。在絕大多數的計算機科學分支領域中，要想完成任何實質性的工作，理解算法的基礎知識並掌握與算法密切相關的數據結構知識是必不可少的。例如，在斯坦福大學，每個級別（學士、碩士和博士）的計算機科學系都需要學習算法課。下面僅僅是算法應用的一些例子。

（1）通信網絡中的路由協議需要使用經典的最短路徑算法。

（2）公鑰加密依賴於高效的數論算法。

（3）計算機圖像學需要用到幾何算法所提供的計算基元（computational primitive）功能。

（4）數據庫的索引依賴於平衡搜索樹這種數據結構。

（5）計算機生物學使用動態編程算法對基因的相似度進行測量。

類似的例子還有很多。

算法是技術革新的推動力。

這種算法最有名的例子是Google當前所使用的網頁排名（PageRank）算法。事實上，在美國白宮2010年12月的一個報告中，總統的科學技術顧問作了如下的描述：

“每個人都知道摩爾定律，它是Intel的共同創立者Gordon Moore於1965年所作的一個預測：集成電路中的半導體密度每過一到兩年就會擴大一倍……在許多領域，由於算法的改進所獲得的性能提升甚至遠遠超過由於處理器速度的急劇增加所帶來的性能提升。”

算法會對其他科學產生影射。雖說這個話題超出了本文的範圍，但算法就像一面“鏡子”一樣，越來越多地用於對計算機科學技術之外的過程進行影射。例如，對量子計算的研究為量子力學提供了一種新的計算視角。經濟市場中的價格波動也可以形象地看作一種算法過程。

甚至，技術革新本身也可以看作一種令人吃驚的有效搜索算法。

學習算法有益於思維。當我還是一名學生時，我最喜歡的課程始終是那些具有挑戰性的課程。當我艱苦地征服這些課程時，我甚至能夠感覺到自己的智商比剛開始學習這些課程時提高了幾個點。我希望本文也能夠為讀者提供類似的體驗。

算法很有趣！最後，我希望讀者在讀完本文後認為算法的設計和分析是件簡單而愉快的事情。這並非易事，因為它需要把精確和創新這兩個特徵罕見地結合在一起。它常常會給我們帶來挫折，但有時會讓我們深深入迷。別忘了，當我們還是小孩子時，就已經開始學習算法了。

整數乘法

1.2.1　問題和解決方案

小學三年級的時候，我們很可能就學習了兩數相乘的計算方法，這是一種具有良好定義的規則，把輸入（2 個數）轉換為輸出（它們的乘積）。在這裡，我們要注意區分兩個不同的概念：一個是對需要解決的問題的描述，另一個是對解決方案所使用方法（也就是問題的算法）的描述。在本文中，我們所採用的模式是首先介紹一個計算問題（輸入及其目標輸出），然後描述一個或多個解決該問題的算法。

在整數乘法問題中，它的輸入是兩

1.2.2　整數乘法問題

個n位數字的整數，分別稱為x和y。x和y的長度n可以是任意正整數，但我鼓勵讀者把n看作一個非常巨大的數，幾千甚至更大。（例如，在有些加密應用程序中，可能需要將兩個非常巨大的數相乘。）整數乘法問題的目標輸出就是x ·y這個乘積。

問題：整數乘法

輸入：兩個n位數字的非負整數x和

輸出：x和y的乘積。

1.2.3　小學算法

精確地定義了計算問題之後，我們描述一種解決該問題的算法，這種算法和我們在小學三年級時所學習的算法是一樣的。我們通過測量它所執行的“基本操作”的數量來評估這種算法的性能。現在，我們可以把基本操作看作下列的操作之一：

（1）兩個個位數相加；

（2）兩個個位數相乘；

（3）在一個數的之前或之後添加一個0。

為了加深記憶，我們討論一個具體的例子，把x = 5678和y = 1234（因此n = 4）這兩個整數相乘。詳細過程如圖1.1所示。這種算法首先計算第一個數與第二個數最後一位數字的“部分乘積”：5678×4 = 22 712。計算這個部分乘積的過程又可以細分為把第一個數的每位數字與4相乘，並在必要時產生“進位”。在計算下一個部分乘積（5678×3 = 17 034）時，我們執行相同的操作，並把結果左移一位，相當於在末尾添加一個“0”。對於剩下的兩個部分乘積，也是執行相同的操作。最後一個步驟就是把所有的4個部分乘積相加。

圖1.1　整數相乘的小學生算法

回想小學三年級的時候，我們接受了這種算法的正確性。也就是說，不管x和y是什麼整數，只要所有的中間計算過程都是正確的，這種算法最終能夠得出兩個輸入數x和y的正確乘積。

也就是說，我們絕不會得到錯誤的答案，並且它不會陷入無限循環。

1.2.4　操作數量的分析

小學老師很可能不會討論實現整數相乘這個過程所需要的基本操作的數量。為了計算第一個部分乘積，我們把4依次與第1個數的5、6、7、8相乘，這樣就產生了4個基本操作。由於進位的原因，我們還需要執行一些加法操作。

一般而言，計算一個部分乘積涉及n個乘法（每位數字1個）以及最多

基本操作的數量 ≤ 常數（此例中為2）· n2

可以想象，當輸入數的位數越來越多時，這種算法所執行的基本操作的數量也會急劇增加。如果把輸入數的位數增加一倍，需要執行的基本操作的數量是原來的4倍。如果輸入的位數是原來的4倍，那麼基本操作的數量就是原來的16倍，以此類推。

1.2.5　還能做得更好嗎

由於讀者所接受的小學教育略有差異，有些讀者可能會覺得上面這種方法是唯一可行的，還有些讀者認為它至少是兩數相乘最合適的方法之一。如果想成為一名嚴肅的算法設計師，那你必須要擺脫這種認為舊有方法理所當然的順從思維。

Aho、Hopcroft和Ullman的經典算法名著在討論了一些算法設計範式之後，對於這個問題提出了自己的見解：

“或許，成為優秀算法設計師的最重要原則就是拒絕滿足。”

或者如我所歸納的，每一名算法設計師都應該堅守下面這個信條：

我還能做得更好嗎？

當我們面對一個計算問題的簡單解決方案時，這個問題就顯得格外合適。在小學三年級時，老師不可能要求我們對這種簡單的整數相乘算法進行改進。但是到了現在這個時候，無疑是提出這個問題的良好時機。

Karatsuba乘法

算法設計的空間之豐富達到了令人吃驚的程度，除了小學三年級所學習的方法之外，肯定還有其他有趣的方法可以實現兩個整數的乘法。本節描述了一種名為Karatsuba乘法的方法。

1.3.1　一個具體的例子

為了讓讀者更方便了解Karatsuba乘法，我們還是沿用前面的x = 5678和y = 1234這個例子。我們將執行一系列與之前的小學算法截然不同的步驟，最終也生成x · y這個乘積。這些步驟序列可能會讓讀者覺得非常神秘，就像魔術師突然從自己的帽子裡拽出一隻兔子一樣。在本節的後面，我們將介紹什麼是Karatsuba乘法，並解釋它的工作原理。現在，我們需要領悟的一個關鍵要點就是我們可以通過許多令人眼花繚亂的方法來解決諸如整數乘法這樣的計算問題。

首先，我們把x的前半部分和後面部分劃分開來，並分別為它們命名為a

類似，c和d分別表示12和34（圖1.2）。

圖1.2　把一個4位整數看成是一對兩位整數

接著，我們執行一系列的操作，它們只涉及兩位數a、b、c和d，並最終用一種神奇的方法把它們組合在一起，產生x和y的乘積。

步驟1：計算a · c = 56 × 12，其結果為672（歡迎讀者驗算）。

步驟2：計算b · d = 78 × 34 = 2652。

接下來的兩個步驟顯得更加神秘：

步驟3：計算( a + b)

步驟4：步驟3的結果減去前兩個步驟的結果6164 – 672 – 2562 = 2840。

最後，我們把步驟1、2、4的結果相加，不過在此之前先在步驟1的結果後面加上4個0，在步驟4的結果後面加上2個0。

步驟5：計算104×672 + 102 × 2840 + 2652 = 6 720 000 + 284 000 + 2652 = 7 006 652。

這個結果與第1.2節的小學算法所產生的結果完全相同！

讀者肯定不明白這中間到底發生了什麼。我希望讀者既對此感到困惑，又為此入迷，並且非常愉快地發現除了小學所學習的整數相乘算法之外，還存在其他完全不同的算法。一旦意識到算法空間之廣闊，我們就會萌生這樣的想法：我們能不能比小學算法做得更好？上面所描述的這種算法是不是更加優秀？

1.3.2　一種遞歸算法

在詳細分析Karatsuba乘法之前，我們先探索一種更簡單的處理整數乘法的遞歸方法 。整數乘法的遞歸算法大致可以理解為調用更少位數的整數乘法（例如在上面的例子中，先執行12、34、56、78這些整數的乘法）。

一般而言，位數為偶數n的數x可以表示為2個n/2位的數，即它的前半部分a和後半部分b：

x = 10n/2 · a + b

類似，我們也可以得到下面的結果：

y = 10n/2 · c + d

為了計算x和y的乘積，我們使用上面這兩個表達式並把它們相乘：

x

= 10n · ( a · c) + 10n/2 · ( a · d + b · c ) + b · d （1.1）

注意，表達式（1.1）中的所有乘法要麼是在一對n/2位的整數之間進行的，要麼涉及10的乘方。

表達式（1.1）提示用一種遞歸方法進行兩個整數的相乘。為了計算 x

RecIntMult

輸入：兩個n位正整數x和y。

輸出：x和y的乘積。

先決條件：n是2的整數次方。

​RecIntMult算法和小學算法相比是更快還是更慢呢？現在讀者對這個問題應該不會有直觀的感覺，我們將在第4章討論這個問題的答案。

1.3.3　Karatsuba乘法

Karatsuba乘法是RecIntMult算法的一種優化版本。我們仍然從根據a、b、c、d進行了擴展的x·y表達式（1.1）開始。RecIntMult算法使用了4個遞歸調用，分別用於表達式（1.1）中的每個n/2位數之間的乘積。我們事實上並不真正關心a · d或b · c，只是關注它們的和a ·

為了觀察這種想法是否可行，我們首先像前面一樣以遞歸的方式調用a · c和b · d。

步驟1：用遞歸的方式計算a · c。

我們不再遞歸地計算a · d 或b · c，而是遞歸地計算a + b和c + d的乘積。

步驟3：計算a + b和c + d（使用小學加法），並以遞歸的方式計算(a + b)·(c + d)。

Karatsuba乘法所使用的關鍵技巧來源於19世紀早期的著名數學家Carl Friedrich Gauss，這是他在思考複數乘法時所想到的方法。從步驟3的結果中減去前兩個步驟的結果所得到的值正是我們所需要的，也就是表達式（1.1）中a · d + b · c的中間係數：

步驟4：從步驟3的結果中減去前兩個步驟的結果，獲得a · d + b · c的值。

最後一個步驟就是計算表達式（1.1），其方法與RecIntMult算法相同。

步驟5：在步驟1的結果後面加上n個0，在步驟4的結果後面加上n/2個0，然後將它們與步驟2的結果相加，以計算表達式（1.1）。

​Karatsuba乘法只進行了3個遞歸調用！節省1個遞歸調用應該能夠節省整體運行時間，但能夠節省多少呢？Karatsuba算法是不是比小學乘法更快？答案並不顯而易見，不過我們將在第4章引入一個方便的應用工具，用於對這類分治算法的運行時間進行分析。

MergeSort算法

在本節中，我們第一次對一個具有相當深度的算法的運行時間進行分析，這個算法就是著名的MergeSort（歸併排序）算法。

1.4.1　推動力

MergeSort是一種相對古老的算法，早在1945年就由約翰·馮·諾依曼提出並廣為人知。我們為什麼要在現代的算法課程中討論這樣的古老例子呢？

薑還是老的辣。儘管已經70歲“高齡”，但MergeSort仍然是一種可供選擇的排序算法。它在實踐中被一直沿用，仍然是許多程序庫中的標準排序算法之一。

經典的分治算法。分治算法設計範式是一種通用的解決問題的方法，在許多不同的領域有著大量的應用。它的基本思路就是把原始問題分解為多個更小的子問題，並以遞歸的方式解決子問題，最終通過組合子問題的解決方案得到原始問題的答案。MergeSort可以作為一個良好的起點，幫助我們理解分治算法範式以及它的優點，包括它所面臨的分析挑戰。

校準預備條件。本節對MergeSort的討論可以讓讀者明白自己當前的技術水平是否適合閱讀本文。我假設讀者具有一定的編程和數學背景（具有一定實踐經驗），能夠把MergeSort的高級思路轉換為自己所喜歡的編程語言的工作程序，並且能夠看懂我們對算法所進行的運行時間分析。如果讀者能夠適應本節和下一節的內容，那麼對於本文的剩餘部分也不會有什麼問題。

推動算法分析的指導原則。本節對MergeSort運行時間的分析展示了一些更加基本的指導原則，例如探求每個特定長度的輸入的運行時間上界以及算法的運行時間增長率的重要性（作為輸入長度的函數）。

為主方法熱身。我們將使用“遞歸樹方法”對MergeSort進行分析，這是一種對遞歸算法所執行的操作進行累計的方法。第4章將集合這些思路生成一個“主方法”。主方法是一種功能強大且容易使用的工具，用於界定許多不同的分治算法的運行時間，包括第1.3節所討論的RecIntMult和Karatsuba算法。

1.4.2　排序

讀者很可能對排序問題以及一些解決排序問題的算法已經有所瞭解，我們姑且把它們放在一起。

問題：排序

輸入：一個包含n個數的數組，以任意順序排列。

輸出：包含與輸入相同元素的數組，但它們已經按照從小到大的順序排列。

例如，假設輸入數組是：

目標輸出數組是：

在上面這個例子中，輸入數組中的8個數是各不相同的。即使數組中出現了重複的數，排序也不會變得更困難，甚至變得更簡單。但是，為了儘可能地簡單，我們假設輸入數組中的數總是不同的。我積極鼓勵讀者對我們所討論的排序算法進行修改（如果可以修改），使之能夠處理重複的值。

如果讀者並不關注運行時間的優化，那麼要想實現一種正確的排序算法並不困難。也許最簡單的方法就是首先對輸入數組進行掃描，找到最小的元素並把它複製到輸出數組的第1個元素，接著掃描並複製次小的元素，接下來依次類推。這種算法稱為SelectionSort（選擇排序）。讀者可能聽說過InsertionSort（插入排序），這是同一個思路的一種更靈巧的實現方法，它把輸入數組中的每個元素依次插入到有序的輸出數組中的適當位置。讀者可能還聽說過BubbleSort（冒泡排序），它需要對一對對相鄰的無序元素進行比較，並執行反覆的交換，直到整個數組實現了排序。所有這些算法所需要的運行時間都是平方級的，意味著對長度為n的數組所執行的操作數量級是

1.4.3　一個例子

理解MergeSort最容易的方法就是通過一個具體的例子（圖1.3）。我們將使用1.4.2節的輸入數組。

作為一種遞歸的分治算法，MergeSort以更小的輸入數組調用自身。把一個排序問題分解為多個更小的排序問題的最簡單方法就是把輸入數組對半分開，並分別以遞歸的方式對數組的前半部分和後半部分進行排序。例如，在圖1.3中，輸入數組的前半部分和後半部分分別是{5, 4, 1, 8}和{7, 2, 6, 3}。通過神奇的遞歸（如果讀者喜歡，也可以稱為歸納），第一個遞歸調用對前半部分進行正確的排序，返回數組{1, 4, 5, 8}。第二個遞歸調用則返回數組{2, 3, 6, 7}。

圖1.3　通過一個具體例子領會MergeSort

最後的“歸併”步驟把這兩個已經排序的長度為4的數組組合為一個已經排序的包含8個數的數組。下面描述了這個步驟的細節，其思路是通過索引遍歷每個已經排序的子數組，並按照從左到右的有序方式生成輸出數組。

1.4.4　偽碼

圖1.3大致相當於下面的偽碼。對於通用的問題，它有兩個遞歸調用和一個歸併步驟。和往常一樣，我們的描述並不需要逐行轉換為工作代碼（儘管已經相當接近）。

​這段偽碼省略了一些內容，這些內容值得予以說明。作為一種遞歸算法，它必須有一個或多個基本條件，如果不再有進一步的遞歸，就直接返回答案。因此，如果輸入數組A只包含0個或1個元素，MergeSort就返回該數組（它顯然已經排序）。這段偽碼並沒有詳細說明當n是奇數時，“前半部分”和“後半部分”是怎麼劃分的，但那種顯而易見的理解（其中一半比另一半多一個元素）是可行的。最後，這段偽碼忽略了怎麼把兩個子數組實際傳遞給它們各自的遞歸調用的實現細節。這些細節取決於編程語言。高級偽碼的要點就是忽略這類細節，把注意力集中在超越任何特定編程語言的概念上。

1.4.5　Merge子程序

我們應該怎樣實現歸併步驟呢？此時，兩個遞歸調用已經完成了它們的工作，我們擁有了兩個已經排序的長度為n/2的子數組C

​我們根據索引k遍歷輸出數組，根據索引i

和往常一樣，我們的偽碼有意寫得比較粗略，這是為了強調整片森林而不是具體的樹木。完整的實現應該要追蹤C或D是否已經遍歷到了數組的末尾，此時就把另一個數組的所有剩餘元素都複製到數組B的最後部分（按順序）。現在，就是讀者自行實現MergeSort算法的好時機。

本文要點

• 算法是一組具有良好定義的規則，用於解決一些計算問題。
• 我們在小學時學習的兩個
  n位整數相乘算法所執行的基本操作的數量與n的平方成正比。
• Karatsuba乘法是一種用於整數乘法的遞歸算法，它使用了高斯提出的技巧，它比一種更簡單的遞歸算法節省了一個遞歸調用。
• 在思考和交流算法時，經驗豐富的程序員和計算機科學家使用高級描述而不是詳細的實現。
• MergeSort算法是一種“分治”算法，它把輸入數組分為兩個部分，採用遞歸的方法對每個部分進行排序，然後使用Merge子程序把它們的結果組合在一起。
• 忽略常數因子和低階項，MergeSort對n個元素所執行的操作數量的增長類似於函數n log2 n。我們在分析時使用遞歸樹對所有的遞歸調用所完成的工作進行方便的組織。
• 由於函數log2 n在n增長時增長較緩，所以MergeSort在一般情況下比更簡單的排序算法速度更快，後者的運行時間與輸入長度的平方成正比。對於較大的
  n，這種算法的性能提高是非常明顯的。
• “快速算法”是指算法的最壞情況運行時間隨著輸入長度的增長而較緩慢地增長。
• “無代價基本算法”是指算法具有線性或近線性運行時間，比讀取輸入所需要的時間多不了多少。

《算法詳解（卷1）——算法基礎》

Tim Roughgarden 著

算法詳解系列圖書共有4卷，本書是第一卷——基礎算法。本書共有6章，主要介紹了4個主題，它們分別是漸進性分析和大O表示法、分冶算法和主方法、隨機化算法以及排序和選擇。附錄A和附錄B簡單介紹了數據歸納法和離散概率的相關知識。本書的每一章均有小測驗、章末習題和編程題，這為讀者的自我檢查以及進一步學習提供了較多的便利。

閱讀更多 異步社區 的文章

關鍵字: 數據結構 量子計算 生物