本書是作者20多年在國內外教學與科研實踐的結晶，深入淺出地介紹計算機算法中涉及的基本理論和方法。主要內容包括算法復雜度的概念和表達、分治法、貪心法、動態規劃、圖的遍歷技術、平掃線技術、回溯法、分支限界法、(((剪枝等。在講述這些理論和方法的同時，介紹一系列重要問題的算法，包括排序問題、選擇問題、最小支撐樹問題、最短路徑問題、網絡流問題、二分圖的匹配問題、字符串的匹配問題以及若干幾何算法問題，并將這些問題的解法及所用技術緊密相連，有機地編排在一起。此外，本書還介紹了問題本身固有的計算復雜性的概念和NP完全問題的理論以及近似算法。
本書講解細膩、分析透徹，以探索解決問題的方式深入分析了大量案例，使讀者能清晰觸摸到作者的思維方法，并建立起自己獨立思考的學習習慣。本書可以作為計算機科學等相關專業本科生、研究生的教材，也可供從事計算機算法設計與分析工作的教師與研究人員參考。
目 錄
前言
教學建議
第1章 概述
1.1 算法與數據結構及程序的關系
1.1.1 什么是算法
1.1.2 算法與數據結構的關系
1.1.3 算法與程序的關系
1.1.4 選擇排序的例子
1.1.5 算法的偽碼表示
1.2 算法復雜度分析
1.2.1 算法復雜度的度量
1.2.2 算法復雜度與輸入數據規模的關系
1.2.3 輸入數據規模的度量模型
1.2.4 算法復雜度分析中的兩個簡化假設
1.2.5 最好情況、最壞情況和平均情況的復雜度分析
1.3 函數增長漸近性態的比較
1.3.1 三種比較關系及O、Ω、Θ記號
1.3.2 表示算法復雜度的常用函數
1.4 算法復雜度與問題復雜度的關系
1.4.1 問題復雜度是算法復雜度的下界
1.4.2 問題復雜度與最佳算法
1.4.3 易處理問題和難處理問題
習題
第2章 分治法
2.1 分治法原理
2.1.1 二元搜索的例子
2.1.2 表示復雜度的遞推關系
2.2 遞推關系求解
2.2.1 替換法
2.2.2 序列求和法和遞歸樹法
2.2.3 常用序列和公式
2.2.4 主方法求解
習題
第3章 基于比較的排序算法
3.1 插入排序
3.1.1 插入排序的算法
3.1.2 插入排序算法的復雜度分析
3.1.3 插入排序的優缺點
3.2 合并排序
3.2.1 合并算法及其復雜度
3.2.2 合并排序的算法及其復雜度
3.2.3 合并排序的優缺點
3.3 堆排序
3.3.1 堆的數據結構
3.3.2 堆的修復算法及其復雜度
3.3.3 為輸入數據建堆
3.3.4 堆排序算法
3.3.5 堆排序算法的復雜度
3.3.6 堆排序算法的優缺點
3.3.7 堆用作優先隊列
3.4 快排序
3.4.1 快排序算法
3.4.2 快排序算法最壞情況復雜度
3.4.3 快排序算法平均情況復雜度
3.4.4 快排序算法最好情況復雜度
3.4.5 快排序算法優缺點
習題
第4章 不基于比較的排序算法
4.1 比較排序的下界
4.1.1 決策樹模型及最壞情況下界
*4.1.2 二叉樹的外路徑總長與平均情況下界
*4.1.3 二叉樹的全路徑總長及堆排序最好情況下界
4.2 不基于比較的線性時間排序算法
4.2.1 計數排序
4.2.2 基數排序
4.2.3 桶排序
習題
第5章 中位數和任一順序數的選擇
5.1 問題定義
5.2 最大數和最小數的選擇
5.2.1 最大和最小順序數的選擇算法及其復雜度
5.2.2 同時找出最大數和最小數的算法
5.3 線性時間找出任一順序數的算法
5.3.1 最壞情況復雜度為O (n)的算法
5.3.2 平均情況復雜度為O (n)的算法
5.4 找出k個最大順序數的算法
5.4.1 一個理論聯系實際的問題
5.4.2 利用堆來找k個最大的順序數的算法
5.4.3 利用錦標賽樹來找k個最大順序數的算法
習題
第6章 動態規劃
6.1 動態規劃的基本原理
6.2 矩陣連乘問題
6.3 最長公共子序列問題
*6.4 最佳二元搜索樹
6.5 多級圖及其應用
6.6 最長遞增子序列問題
習題
第7章 貪心算法
7.1 最佳郵局設置問題
7.2 最佳活動安排問題
7.3 哈夫曼編碼問題
7.3.1 前綴碼
7.3.2 最佳前綴碼——哈夫曼編碼
7.4 最佳加油計劃問題
習題
第8章 圖的周游算法
8.1 圖的表示
8.1.1 鄰接表
8.1.2 鄰接矩陣
8.2 廣度優先搜索及應用
8.2.1 廣度優先搜索策略
8.2.2 廣度優先搜索算法及距離樹
8.2.3 無向圖的二著色問題
8.3 深度優先搜索及應用
8.3.1 深度優先搜索策略
8.3.2 深度優先搜索算法和深度優先樹
8.3.3 深度優先搜索算法舉例和圖中邊的分類
8.3.4 拓撲排序
8.3.5 無回路有向圖中最長路徑問題及應用
8.3.6 有向圖的強連通分支的分解
8.3.7 無向圖的雙連通分支的分解
習題
第9章 圖的最小支撐樹
9.1 計算最小支撐樹的一個通用的貪心算法策略
9.2 Kruskal算法
9.3 Prim算法
習題
第10章 單源最短路徑
10.1 Dijkstra算法
10.2 Bellman-Ford算法
習題
第11章 網絡流
11.1 網絡模型和最大網絡流問題
11.2 網絡中流與割的關系
11.2.1 網絡中的割及其容量
11.2.2 剩余網絡和增廣路徑
11.2.3 最大流最小割定理
11.3 Ford-Fulkerson 方法
11.3.1 Ford-Fulkerson 的通用方法
11.3.2 Edmonds-Karp算法
11.3.3 Dinic算法
11.3.4 0-1網絡的最大流問題
11.4 二部圖的匹配問題
11.4.1 用網絡流求二部圖的最大匹配算法
11.4.2 Philip-Hall婚配定理
11.4.3 Birkhoff-von Neuman定理
11.5 推進-重標號算法簡介
11.5.1 預流和高度函數
11.5.2 在剩余圖中對頂點的兩個操作
11.5.3 推進-重標號算法的初始化
11.5.4 推進-重標號的通用算法
習題
第12章 計算幾何基礎
12.1 平面線段及相互關系
12.1.1 向量的點積和叉積
12.1.2 平面線段的相互關系
12.2 平掃線技術和線段相交的確定
12.2.1 平掃線的狀態
12.2.2 用平掃線確定線段相交的算法
12.3 平面點集的凸包
12.3.1 Graham掃描法
12.3.2 Jarvis 行進法
12.4 最近點對問題
習題
第13章 字符串匹配
13.1 一個樸素的字符串匹配算法
13.2 Rabin-Karp算法
13.3 基于有限狀態自動機的匹配算法
13.3.1 有限狀態自動機簡介
13.3.2 字符串匹配自動機
13.3.3 基于有限狀態自動機的串匹配算法
13.4 Knuth-Morris-Pratt（KMP）算法
13.4.1 模式的前綴函數
13.4.2 KMP算法的偽碼
習題
第14章 NP完全問題
14.1 預備知識
14.1.1 圖靈機
14.1.2 符號集和編碼對計算復雜度的影響
14.1.3 判斷型問題和優化型問題及其關系
14.1.4 判斷型問題的形式語言表示
14.1.5 多項式關聯和多項式歸約
14.2 P和NP語言類
14.2.1 非確定圖靈機和NP語言類
14.2.2 多項式檢驗算法和NP類語言
14.3 NP完全語言類和NP完全問題
14.3.1 第一個NPC問題
14.3.2 若干著名NPC問題的證明
習題
第15章 近似算法
15.1 近似算法的性能評價
15.2 頂點覆蓋問題
15.3 貨郎擔問題
15.3.1 滿足三角不等式關系的貨郎擔問題
15.3.2 無三角不等式關系的一般貨郎擔問題
15.4 集合覆蓋問題
15.5 MAX-3-SAT問題
15.6 加權的頂點覆蓋問題
15.7 子集和問題
15.7.1 一個保證最優解的指數型算法
15.7.2 子集和問題的一個完全多項式近似機制
*15.8 鴻溝定理和不可近似性
15.8.1 鴻溝定理
15.8.2 任務均勻分配問題
習題
第16章 窮舉搜索
16.1 搜索問題及方法的描述
16.2 回溯法
16.2.1 回溯法的通用算法
16.2.2 n皇后問題
16.2.3 子集和問題
16.2.4 回溯法的效率估計
16.3 分支限界法
16.3.1 分支限界法解n皇后問題
16.3.2 0/1背包問題
16.4 博弈樹和α-β剪枝
16.4.1 博弈樹及其評估的方法
16.4.2 α-β剪枝法
習題
附錄 紅黑樹
參考文獻
新書資訊