前言

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

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

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

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

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

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

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

法。

本書算法均采用 Python語言進(jìn)行描述， Python是一類解釋性語言，其語法

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

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

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

與采用偽代碼描述算法的書比較而言，采用 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)。本書的內(nèi)容

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

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

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

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

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

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

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

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

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

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

本書主要內(nèi)容

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

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

、文字翻譯，甚至

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

圖 1本書的主線 轉(zhuǎn)化

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

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

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

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

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

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

和穩(wěn)定匹配這三個(gè)有趣的問題，幫助讀者熟悉 Python語言。第 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)一步熟悉采用遞歸求解問題的過程

。

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

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

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

，幫助讀者明確哪類問題可解，而哪類問題目前不可解。

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

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

如何使用本書

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

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

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

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

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

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

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

前言 III

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

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

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

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

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

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

。

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

及改進(jìn)算法。

掌握哈希表的基本概念。

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

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

。 2

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

表示。

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

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

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

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

了解文檔比較問題及其算法。 2

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

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

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

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

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

熟練掌握常見問題的遞歸求解方法。熟悉回文、全排列和漢諾塔問題的遞歸

算法。

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

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

續(xù)表

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

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

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

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

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

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

刪除和查找等。

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

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

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

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

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

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

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

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

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

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

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

場(chǎng)景。

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

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

過程。

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

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

過程。

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

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

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

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

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

單源最短路徑和最小生成樹。理解單源最短路徑和

最小生成樹算法中，利用合理的數(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)化問題的典型步驟，以及動(dòng)態(tài)規(guī)

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

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

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

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

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

間的關(guān)系。 2

掌握通過增廣路徑求最大流問題的 Ford-Fulkerson和 Edmond-Karp算法，

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

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

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

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

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

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

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

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

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

本分類。 2

理解 P問題、 NP問題和 NPC問題的定義。

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

為重要的問題之一。

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

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

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

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

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

上的題目

① https://leetcode com/

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

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

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

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

一門程序語言課程之后較為合適。

致謝

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

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

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

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

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

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

成書稿。

程振波李曲王春平

2017年 6月