前言

算法設(shè)計(jì)與分析是計(jì)算機(jī)專(zhuān)業(yè)非常重要的一門(mén)基礎(chǔ)課程，它不僅是諸多

計(jì)算機(jī)專(zhuān)業(yè)課程的基礎(chǔ)，也是許多信息科技類(lèi)公司招聘程序員時(shí)，筆試與面

試重點(diǎn)考核的內(nèi)容。算法設(shè)計(jì)與分析已經(jīng)有了諸多經(jīng)典的著作，比如美國(guó)麻

省理工學(xué)院（ MIT）幾位教授合著的《算法導(dǎo)論》 ①等。然而，這些經(jīng)典著

作當(dāng)作教材使用時(shí)，都會(huì)存在對(duì)內(nèi)容進(jìn)行適當(dāng)裁剪，以便更適合 48或者 32

個(gè)學(xué)時(shí)教學(xué)的問(wèn)題。我們寫(xiě)本書(shū)的目的就是對(duì)初等算法內(nèi)容進(jìn)行合理的編排

，讓初學(xué)者能很快地掌握解決計(jì)算問(wèn)題的常用算法，以及分析算法效率的方

法。

本書(shū)算法均采用 Python語(yǔ)言進(jìn)行描述， Python是一類(lèi)解釋性語(yǔ)言，其語(yǔ)法

簡(jiǎn)單直觀(guān)，有一定程序設(shè)計(jì)基礎(chǔ)的學(xué)生可以很快入門(mén)。 Python語(yǔ)法簡(jiǎn)單并不

意味著功能弱，它在科學(xué)計(jì)算、 Web應(yīng)用等諸多領(lǐng)域都有著廣泛的應(yīng)用。國(guó)

外知名的高校，如麻省理工學(xué)院，也在算法設(shè)計(jì)課中采用 Python語(yǔ)言描述。

與采用偽代碼描述算法的書(shū)比較而言，采用 Python描述算法能給讀者直接的

運(yùn)算結(jié)果，從而可以使讀者更易于揣摩算法實(shí)現(xiàn)的技巧。

計(jì)算機(jī)算法不僅涉及諸多理論，還有各種技術(shù)細(xì)節(jié)。比如介紹隨機(jī)算法時(shí)，

有些執(zhí)行時(shí)間的分析就需要較多的概率論知識(shí)；而算法實(shí)現(xiàn)技術(shù)細(xì)節(jié)則不僅

關(guān)注如何存儲(chǔ)數(shù)據(jù)，甚至對(duì)執(zhí)行算法的硬件環(huán)境也會(huì)考慮在內(nèi)。本書(shū)的內(nèi)容

安排則介于兩者之間，在數(shù)學(xué)分析與實(shí)現(xiàn)之間期望取得合理的平衡。首先，

在分析算法效率時(shí)盡量避免過(guò)深的數(shù)學(xué)證明，但關(guān)鍵步驟依然會(huì)給出直觀(guān)的

解釋。其次，在實(shí)現(xiàn)算法時(shí)本書(shū)盡量利用 Python已有的數(shù)據(jù)結(jié)構(gòu)和庫(kù)函數(shù)，

從而簡(jiǎn)化算法實(shí)現(xiàn)的技術(shù)難度。

如果將要處理的數(shù)據(jù)、問(wèn)題看作是食材，那么算法就是將食材轉(zhuǎn)化成各

種令人垂涎的美食的過(guò)程。中國(guó)菜肴到處都是充滿(mǎn)想象力的轉(zhuǎn)化，將原本普

通的食材（如大豆和糯米等）轉(zhuǎn)化為營(yíng)養(yǎng)和美味的食物（豆腐、酒釀和醬料

等）。本書(shū)的主線(xiàn)就是轉(zhuǎn)化，它不僅有問(wèn)題的轉(zhuǎn)化，也有方法的轉(zhuǎn)化（如圖

1所示）。通過(guò)問(wèn)題的轉(zhuǎn)化將問(wèn)題化繁為簡(jiǎn)，通過(guò)方法的轉(zhuǎn)化以便融會(huì)貫

通各種算法設(shè)計(jì)的技巧。

本書(shū)主要內(nèi)容

由于計(jì)算機(jī)已經(jīng)成為現(xiàn)代科技、生活不可缺少的工具。因此，解決計(jì)算問(wèn)題

的算法涉及的內(nèi)容可以說(shuō)包羅萬(wàn)象，從簡(jiǎn)單的排序和查找到復(fù)雜的語(yǔ)音識(shí)別

、文字翻譯，甚至

①見(jiàn)參考文獻(xiàn) [1]。

圖 1本書(shū)的主線(xiàn) 轉(zhuǎn)化

游戲等都離不開(kāi)算法。本書(shū)內(nèi)容涵蓋了大部分的經(jīng)典算法，主要內(nèi)容包括遞

歸算法、分治算法、排序算法、動(dòng)態(tài)規(guī)劃算法、圖搜索算法、最大流算法、

隨機(jī)算法和算法復(fù)雜度。

第 1章主要介紹算法的基本概念，通過(guò)實(shí)例向讀者展示解決同一問(wèn)題的不同

算法的確存在效率上顯著的差異。第 2章介紹度量算法效率的記號(hào)，以及分

析簡(jiǎn)單函數(shù)執(zhí)行時(shí)間的常用技巧。第 3章通過(guò)解決文檔比較、單詞拼寫(xiě)糾正

和穩(wěn)定匹配這三個(gè)有趣的問(wèn)題，幫助讀者熟悉 Python語(yǔ)言。第 4章介紹了遞

歸算法以及遞歸函數(shù)求解，從而為后續(xù)章節(jié)復(fù)雜的算法設(shè)計(jì)與分析打下一定

的基礎(chǔ)。第 5章介紹了組織數(shù)據(jù)的兩個(gè)常用方法：排序和數(shù)據(jù)結(jié)構(gòu)，主要強(qiáng)

調(diào)遞歸在組織數(shù)據(jù)中的應(yīng)用，幫助讀者進(jìn)一步熟悉采用遞歸求解問(wèn)題的過(guò)程

。

第 6章到第 11章則分別介紹了分治算法、圖搜索、貪心、動(dòng)態(tài)規(guī)劃、最大流

和隨機(jī)算法。通過(guò)各種有趣的問(wèn)題，向讀者展示轉(zhuǎn)化的基本技巧，以便更好

地幫助讀者建立采用算法思維去解決問(wèn)題的習(xí)慣。第 12章介紹了算法復(fù)雜度

，幫助讀者明確哪類(lèi)問(wèn)題可解，而哪類(lèi)問(wèn)題目前不可解。

本書(shū)由程振波總體設(shè)計(jì)和規(guī)劃。第 2到第 12章由程振波編寫(xiě)，第 1章由程振

波、李曲和王春平編寫(xiě)。全書(shū)由程振波統(tǒng)稿。

如何使用本書(shū)

本書(shū)的內(nèi)容框架是筆者在浙江工業(yè)大學(xué)算法設(shè)計(jì)與分析課程的講義，內(nèi)

容的編排則參考了 MIT的算法課程 6 006。①因此，本書(shū)從內(nèi)容安排來(lái)說(shuō)非

常適合學(xué)時(shí)為 48或者 32學(xué)時(shí)的算法課程。對(duì)于教師而言，可以直接按照本

書(shū)的章節(jié)安排教學(xué)計(jì)劃。為了便于教師安排教學(xué)，具體的教學(xué)建議如下：

① MIT將算法設(shè)計(jì)與分析課程分解成了兩門(mén)課。一門(mén)是 6 006，該課程

主要是算法的入門(mén)課程，可以面向各個(gè)專(zhuān)業(yè)開(kāi)設(shè)。另一門(mén)則是 6 046，這是

一門(mén)面向有一定算法基礎(chǔ)的學(xué)生開(kāi)設(shè)的算法課程。

前言 III

教學(xué)內(nèi)容學(xué)習(xí)要點(diǎn)及教學(xué)內(nèi)容課時(shí)安排

第 1章引言 掌握算法的定義。了解算法的來(lái)源，理解現(xiàn)實(shí)生活中解決問(wèn)題

的辦法與算法之間的關(guān)系；掌握衡量算法的屬性，尤其是正確性和時(shí)間效率

對(duì)算法的意義。 2

掌握算法效率的基本概念。理解直接計(jì)算某個(gè)輸入規(guī)模的時(shí)間來(lái)衡量算法效

率的不足；了解漸進(jìn)分析法以及多項(xiàng)式時(shí)間復(fù)雜度與指數(shù)時(shí)間復(fù)雜度的區(qū)別

。

了解求解問(wèn)題可能存在效率不同的算法。掌握求解一維高點(diǎn)問(wèn)題的簡(jiǎn)單算法

及改進(jìn)算法。

掌握哈希表的基本概念。

第 2章漸進(jìn)分析與 Python計(jì)算模型 掌握運(yùn)行算法的簡(jiǎn)化模型。了解單處理

器隨機(jī)訪(fǎng)問(wèn)機(jī)器模型的結(jié)構(gòu)，以及運(yùn)行在該機(jī)器模型上常見(jiàn)指令的執(zhí)行時(shí)間

。 2

掌握算法漸進(jìn)分析的概念。熟悉三種漸進(jìn)函數(shù)的定義，以及常見(jiàn)函數(shù)的漸進(jìn)

表示。

熟練掌握基本函數(shù)的漸進(jìn)分析。熟悉 Python的判斷、循環(huán)語(yǔ)句寫(xiě)法，熟練

掌握 Python的基本數(shù)據(jù)結(jié)構(gòu)的使用。掌握較為復(fù)雜的函數(shù)的時(shí)間復(fù)雜度分析

，如求最大值、二分搜索等。

第 3章問(wèn)題求解與代碼優(yōu)化 基本掌握使用 Python求解較為復(fù)雜的問(wèn)題。

了解文檔比較問(wèn)題及其算法。 2

了解單詞拼寫(xiě)問(wèn)題及其實(shí)現(xiàn)算法。

了解穩(wěn)定匹配問(wèn)題及其實(shí)現(xiàn)算法。

第 4章遞歸算法與遞歸函數(shù) 熟悉遞歸的組成結(jié)構(gòu)。熟練掌握遞歸算法的兩

個(gè)基本組成，以及它們各自的作用。 4或 6

掌握遞歸算法執(zhí)行的過(guò)程。了解遞歸算法在機(jī)器模型中的運(yùn)行過(guò)程。

熟練掌握常見(jiàn)問(wèn)題的遞歸求解方法。熟悉回文、全排列和漢諾塔問(wèn)題的遞歸

算法。

熟練掌握求解標(biāo)準(zhǔn)遞歸函數(shù) T (n) = aT (n/b) f(n)的方法。掌握替換法

和主分析法求解遞歸函數(shù)的過(guò)程，理解主分析法的三類(lèi)條件及其對(duì)應(yīng)的解。

續(xù)表

教學(xué)內(nèi)容 學(xué)習(xí)要點(diǎn)及教學(xué)內(nèi)容 課時(shí)安排

第 5章 排序與樹(shù)結(jié)構(gòu) 熟悉插入排序、選擇排序和合并排序算法。能熟練

4 寫(xiě)出這三個(gè)排序算法的實(shí)現(xiàn)代碼以及它們各自的

時(shí)間復(fù)雜度。 掌握二叉搜索樹(shù)的基本數(shù)據(jù)操作。能從使用場(chǎng)景的

角度理解二叉樹(shù)與數(shù)組、鏈表等數(shù)據(jù)結(jié)構(gòu)的不同。

掌握基于二叉搜索樹(shù)常見(jiàn)的數(shù)據(jù)操作，比如插入、

刪除和查找等。

熟練掌握堆結(jié)構(gòu)的應(yīng)用場(chǎng)景和數(shù)據(jù)操作。熟悉建堆

算法及其時(shí)間復(fù)雜度分析，了解基于堆的排序和合

并 k個(gè)有序序列等應(yīng)用。

第 6章 分治算法 掌握分治算法求解問(wèn)題的三個(gè)基本步驟。 6

掌握利用分治法求解一些典型問(wèn)題，如序列最大差

值區(qū)間、統(tǒng)計(jì)逆序數(shù)、空間點(diǎn)最小距離和序列中第

k小的數(shù)等問(wèn)題。

熟悉如何將問(wèn)題進(jìn)行分解，以及合并子問(wèn)題解的常

用技巧。掌握分治算法的時(shí)間復(fù)雜度分析。

第 7章 圖搜索算法 熟悉圖的兩種常見(jiàn)表示方法，熟練掌握如何在計(jì)算 4

機(jī)中存儲(chǔ)圖。了解圖在計(jì)算機(jī)應(yīng)用領(lǐng)域常見(jiàn)的應(yīng)用

場(chǎng)景。

熟練掌握?qǐng)D上寬度優(yōu)先搜索算法及其算法復(fù)雜度

分析，了解利用寬度優(yōu)先搜索解決計(jì)算問(wèn)題的建模

過(guò)程。

熟練掌握?qǐng)D上深度優(yōu)先搜索算法及其算法復(fù)雜度

分析，了解利用深度優(yōu)先搜索解決計(jì)算問(wèn)題的建模

過(guò)程。

第 8章 貪心算法 了解貪心算法求解優(yōu)化問(wèn)題的過(guò)程。 4

熟練掌握利用貪心算法求解典型的計(jì)算問(wèn)題，如硬

幣找零、間隔任務(wù)規(guī)劃等問(wèn)題。了解利用替換法證

明貪心策略是否能獲得全局最優(yōu)解的過(guò)程。

熟練掌握貪心算法在兩個(gè)典型圖搜索中的應(yīng)用，即

單源最短路徑和最小生成樹(shù)。理解單源最短路徑和

最小生成樹(shù)算法中，利用合理的數(shù)據(jù)結(jié)構(gòu)優(yōu)化算法

復(fù)雜度的技巧。

教學(xué)內(nèi)容 學(xué)習(xí)要點(diǎn)及教學(xué)內(nèi)容 課時(shí)安排

第 9章動(dòng)態(tài)規(guī)劃算法 理解動(dòng)態(tài)規(guī)劃求解優(yōu)化問(wèn)題的典型步驟，以及動(dòng)態(tài)規(guī)

劃算法求解計(jì)算問(wèn)題的時(shí)間復(fù)雜度分析。 6

熟練掌握利用動(dòng)態(tài)規(guī)劃算法求解一維、二維等典型優(yōu)化問(wèn)題，如斐波那契數(shù)

、拾撿硬幣、連續(xù)子序列的最大值、矩陣的括號(hào)、 0-1背包問(wèn)題等。

對(duì)于簡(jiǎn)單問(wèn)題能畫(huà)出其動(dòng)態(tài)規(guī)劃表，并能從中得到問(wèn)題的解。

第 10章最大流算法 掌握最大流問(wèn)題的定義，了解流量、容量以及它們之

間的關(guān)系。 2

掌握通過(guò)增廣路徑求最大流問(wèn)題的 Ford-Fulkerson和 Edmond-Karp算法，

理解這兩個(gè)算法之間的異同。

了解將計(jì)算問(wèn)題轉(zhuǎn)化為最大流問(wèn)題的基本過(guò)程。掌握通過(guò)最大流算法求解二

向圖最大匹配和文件傳輸中的不重合邊等問(wèn)題的方法。

第 11章隨機(jī)算法 了解兩種典型的隨機(jī)算法：蒙特卡洛和拉斯維加斯算法

，以及它們之間的異同。 2

熟練掌握利用隨機(jī)算法求解典型的計(jì)算問(wèn)題，如矩陣乘積結(jié)果驗(yàn)證、快速排

序、選擇第 k小的數(shù)和最小割驗(yàn)證等。

了解隨機(jī)快速排序算法復(fù)雜度分析過(guò)程。

第 12章算法復(fù)雜度 了解如何根據(jù)問(wèn)題求解的難易程度對(duì)計(jì)算問(wèn)題進(jìn)行基

本分類(lèi)。 2

理解 P問(wèn)題、 NP問(wèn)題和 NPC問(wèn)題的定義。

了解幾個(gè)典型的 NPC問(wèn)題，理解為什么證明 P是否等于 NP是計(jì)算機(jī)領(lǐng)域最

為重要的問(wèn)題之一。

對(duì)學(xué)生而言，先閱讀書(shū)中各章節(jié)內(nèi)容，然后運(yùn)行書(shū)中代碼以便檢驗(yàn)對(duì)算法的

理解程度。特別是，學(xué)生還應(yīng)該獨(dú)立重復(fù)出書(shū)中各個(gè)問(wèn)題的算法，這個(gè)過(guò)程

就好比學(xué)習(xí)圍棋的選手進(jìn)行復(fù)盤(pán)一樣。如果僅僅是了解算法原理，而沒(méi)有通

過(guò)寫(xiě)代碼來(lái)實(shí)現(xiàn)算法，將不利于讀者培養(yǎng)獨(dú)立解決問(wèn)題的能力。

此外，除了課后習(xí)題外，我們還建議學(xué)生在 leetcode ①上刷題。 leetcode

上的題目

① https://leetcode com/

不是國(guó)際計(jì)算機(jī)學(xué)會(huì)（ ACM）的競(jìng)賽題目，而是各大 IT企業(yè)的面試題目。通

過(guò)解題不僅能提高學(xué)生算法設(shè)計(jì)的能力，也對(duì)編程能力有極大提高。

閱讀本書(shū)需要學(xué)生能按照教程（ http://www python org/）配置 Python環(huán)

境，知道如何寫(xiě)一個(gè)簡(jiǎn)單的包括循環(huán)的函數(shù)。因此，該課程安排在學(xué)生上過(guò)

一門(mén)程序語(yǔ)言課程之后較為合適。

致謝

在本書(shū)編寫(xiě)過(guò)程中，許多浙江工業(yè)大學(xué)的同學(xué)閱讀了初稿，尤其感謝李軼、

陳明明、嚴(yán)凡等同學(xué)給出的許多建議。我們的許多同事也對(duì)本書(shū)提出了諸多

寶貴建議，他們是呂慧強(qiáng)、錢(qián)能和黃德才老師。本書(shū)還受到浙江工業(yè)大學(xué)校

級(jí)重點(diǎn)教材資助，特此感謝。對(duì)在本書(shū)出版過(guò)程中付出辛勤勞動(dòng)的清華大學(xué)

出版社的編輯致以特別的謝意。最后，作者程振波要對(duì)他的妻子王玉秀、女

兒程靜萱致以特別的謝意，感謝她們給予的愛(ài)和支持，讓他能心無(wú)旁騖地完

成書(shū)稿。

程振波李曲王春平

2017年 6月