算法設計與分析：C++語言描述（第2版）

第1部分 算法和算法分析
第1章 算法問題求解基礎
1.1 算法概述
1.1.1 什么是算法
1.1.2 為什么學習算法
1.2 問題求解方法
1.2.1 問題和問題求解
1.2.2 問題求解過程
1.2.3 系統(tǒng)生命周期
1.3 算法設計與分析
1.3.1 算法問題求解過程
1.3.2 如何設計算法
1.3.3 如何表示算法
1.3.4 如何確認算法
1.3.5 如何分析算法
1.4 遞歸和歸納
1.4.1 遞歸
1.4.2 遞歸算法示例
1.4.3 歸納證明
本章小結
習題1
第2章 算法分析基礎
2.1 算法復雜度
2.1.1 什么是好的算法
2.1.2 影響程序運行時間的因素
2.1.3 算法的時間復雜度
2.1.4 使用程序步分析算法
2.1.5 算法的空間復雜度
2.2 漸近表示法
2.2.1 大O記號
2.2.2 記號
2.2.3 記號
2.2.4 小o記號
2.2.5 算法按時間復雜度分類
2.3 遞推關系
2.3.1 遞推方程
2.3.2 替換方法
2.3.3 迭代方法
2.3.4 主方法
2.4 分攤分析
2.4.1 聚集方法
2.4.2 會計方法
2.4.3 勢能方法
本章小結
習題2
第3章 伸展樹與跳表
3.1 伸展樹
3.1.1 二叉搜索樹
3.1.2 自調(diào)節(jié)樹和伸展樹
3.1.3 伸展操作
3.1.4 伸展樹類
3.1.5 旋轉(zhuǎn)的實現(xiàn)
3.1.6 插入運算的實現(xiàn)
3.1.7 分攤分析
3.2 跳表
3.2.1 什么是跳表
3.2.2 跳表類
3.2.3 級數(shù)分配
3.2.4 插入運算的實現(xiàn)
3.2.5 性能分析
本章小結
習題3
第2部分 算法設計策略
第4章 基本搜索和遍歷方法
4.1 基本概念
4.2 圖的搜索和遍歷
4.2.1 搜索方法
4.2.2 鄰接表類
4.2.3 廣度優(yōu)先搜索
4.2.4 深度優(yōu)先搜索
4.3 雙連通分量
4.3.1 基本概念
4.3.2 發(fā)現(xiàn)關節(jié)點
4.3.3 構造雙連通圖
4.4 與或圖
4.4.1 問題分解
4.4.2 判斷與或樹是否可解
4.4.3 構建解樹
本章小結
習題4
第5章 分治法
5.1 一般方法
5.1.1 分治法的基本思想
5.1.2 算法分析
5.1.3 數(shù)據(jù)結構
5.2 求最大最小元
5.2.1 分治法求解
5.2.2 時間分析
5.3 二分搜索
5.3.1 分治法求解
5.3.2 對半搜索
5.3.3 二叉判定樹
5.3.4 搜索算法的時間下界
5.4 排序問題
5.4.1 合并排序
5.4.2 快速排序
5.4.3 排序算法的時間下界
5.5 選擇問題
5.5.1 分治法求解
5.5.2 隨機選擇主元
5.5.3 線性時間選擇算法
5.5.4 時間分析
5.5.5 允許重復元素的選擇算法
5.6 斯特拉森矩陣乘法
5.6.1 分治法求解
5.6.2 斯特拉森分治法
本章小結
習題5
第6章 貪心法
6.1 一般方法
6.2 背包問題
6.2.1 問題描述
6.2.2 貪心法求解
6.2.3 算法正確性
6.3 帶時限的作業(yè)排序
6.3.1 問題描述
6.3.2 貪心法求解
6.3.3 算法正確性
6.3.4 可行性判定
6.3.5 作業(yè)排序貪心算法
6.3.6 一種改進算法
6.4 最佳合并模式
6.4.1 問題描述
6.4.2 貪心法求解
6.4.3 算法正確性
6.5 最小代價生成樹
6.5.1 問題描述
6.5.2 貪心法求解
6.5.3 普里姆算法
6.5.4 克魯斯卡爾算法
6.5.5 算法正確性
6.6 單源最短路徑
6.6.1 問題描述
6.6.2 貪心法求解
6.6.3 迪杰斯特拉算法
6.6.4 算法正確性
6.7 磁帶最優(yōu)存儲
6.7.1 單帶最優(yōu)存儲
6.7.2 多帶最優(yōu)存儲
6.8 　貪心法的基本要素
6.8.1 最優(yōu)量度標準
6.8.2 最優(yōu)子結構
本章小結
習題6
第7章 動態(tài)規(guī)劃法
7.1 一般方法和基本要素
7.1.1 一般方法
7.1.2 基本要素
7.1.3 多段圖問題
7.1.4 資源分配問題
7.1.5 關鍵路徑問題
7.2 每對結點間的最短路徑
7.2.1 問題描述
7.2.2 動態(tài)規(guī)劃法求解
7.2.3 弗洛伊德算法
7.2.4 算法正確性
7.3 矩陣連乘
7.3.1 問題描述
7.3.2 動態(tài)規(guī)劃法求解
7.3.3 矩陣連乘算法
7.3.4 備忘錄方法
7.4 最長公共子序列
7.4.1 問題描述
7.4.2 動態(tài)規(guī)劃法求解
7.4.3 最長公共子序列算法
7.4.4 算法的改進
7.5 最優(yōu)二叉搜索樹
7.5.1 問題描述
7.5.2 動態(tài)規(guī)劃法求解
7.5.3 最優(yōu)二叉搜索樹算法
7.6 0/1背包
7.6.1 問題描述
7.6.2 動態(tài)規(guī)劃法求解
7.6.3 0/1背包算法框架
7.6.4 0/1背包算法
7.6.5 性能分析
7.6.6 使用啟發(fā)式方法
7.7 流水作業(yè)調(diào)度
7.7.1 問題描述
7.7.2 動態(tài)規(guī)劃法求解
7.7.3 Johnson算法
本章小結
習題7
第8章 回溯法
8.1 一般方法
8.1.1 基本概念
8.1.2 剪枝函數(shù)和回溯法
8.1.3 回溯法的效率分析
8.2 n-皇后
8.2.1 問題描述
8.2.2 回溯法求解
8.2.3 n-皇后算法
8.2.4 時間分析
8.3 子集和數(shù)
8.3.1 問題描述
8.3.2 回溯法求解
8.3.3 子集和數(shù)算法
8.4 圖的著色
8.4.1 問題描述
8.4.2 回溯法求解
8.4.3 圖著色算法
8.4.4 時間分析
8.5 哈密頓環(huán)
8.5.1 問題描述
8.5.2 哈密頓環(huán)算法
8.6 0/1背包
8.6.1 問題描述
8.6.2 回溯法求解
8.6.3 限界函數(shù)
8.6.4 0/1背包算法
8.7 批處理作業(yè)調(diào)度
8.7.1 問題描述
8.7.2 回溯法求解
8.7.3 批處理作業(yè)調(diào)度算法
本章小結
習題8
第9章 分枝限界法
9.1 一般方法
9.1.1 分枝限界法概述
9.1.2 LC分枝限界法
9.1.3 15謎問題
9.2 求最優(yōu)解的分枝限界法
9.2.1 上下界函數(shù)
9.2.2 FIFO分枝限界法
9.2.3 LC分枝限界法
9.3 帶時限的作業(yè)排序
9.3.1 問題描述
9.3.2 分枝限界法求解
9.3.3 帶時限作業(yè)排序算法
9.4 0/1背包
9.4.1 問題描述
9.4.2 分枝限界法求解
9.4.3 0/1背包算法
9.5 旅行商問題
9.5.1 問題描述
9.5.2 分枝限界法求解
9.6 批處理作業(yè)調(diào)度
9.6.1 問題描述
9.6.2 分枝限界法求解
9.6.3 批處理作業(yè)調(diào)度算法
本章小結
習題9
第3部分 求解困難問題
第10章 NP完全問題
10.1 基本概念
10.1.1 不確定算法和不確定機
10.1.2 可滿足性問題
10.1.3 P類和NP類問題
10.1.4 NP難度和NP完全問題
10.2 Cook定理和證明
10.2.1 Cook定理
10.2.2 簡化的不確定機模型
10.2.3 證明Cook定理
10.3 一些典型的NP完全問題
10.3.1 最大集團
10.3.2 頂點覆蓋