圖書簡介
本書介紹了算法的概念，算法分析的基本理論、過程和方法以及算法設計的基本策略。主要內容包括算法概述、算法效率分析基礎、蠻力法、分治法、分治策略變體——減治策略和變治策略、動態規劃、時空權衡技術、貪心算法、回溯法和分支限界法
目錄
第1章緒論
1.1什麼是算法
1.1.1算法的由來
1.1.2算法的發展
1.1.3算法的例子
1.2重要的問題類型
1.2.1排序
1.2.2查找
1.2.3字元串匹配
1.2.4圖問題
1.2.5組合問題
1.2.6幾何問題
1.2.7數值問題
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.5算法的表示
1.6為什麼學習算法
總結
習題1
第2章算法效率分析基礎
2.1算法分析框架
2.1.1算法分析概述
2.1.2算法正確性分析
2.1.3時空效率分析
2.1.4算法分析過程
2.2漸進符號和基本效率類型
2.2.1三種漸進符號
2.2.2漸進符號的特性
2.2.3基本效率類型
2.3非遞歸算法的數學分析方法
2.4遞歸算法的數學分析
2.4.1遞歸算法的數學分析方法
2.4.2斐波那契數列
2.5算法的其他分析方法
總結
習題2
第3章蠻力法
3.1概述
3.2排序問題
3.2.1選擇排序
3.2.2冒泡排序
3.3查找問題
3.3.1順序查找
3.3.2字元串匹配
3.4幾何問題
3.4.1最近對問題
3.4.2凸包問題
3.5組合問題
3.5.1旅行商問題
3.5.2背包問題
總結
習題3
第4章分治法
4.1概述
4.2分治法的基本策略及步驟
4.2.1分治法的基本策略
4.2.2分治法的基本步驟
4.3排序問題
4.3.1合併排序
4.3.2快速排序
4.4查找問題
4.4.1折半查找
4.4.2二叉樹遍歷及其相關特性
4.5數值計算問題
4.5.1大整數乘法
4.5.2Strassen矩陣乘法
4.6幾何問題
4.6.1用分治法解最近對問題
4.6.2用分治法解凸包問題
4.7分析分治法在安排循環賽中的套用
總結
習題4
第5章分治策略變體——減治策略和變治策略
5.1減治策略
5.1.1插入排序
5.1.2拓撲排序
5.1.3生成組合對象的算法
5.1.4減常因子算法
5.1.5減可變規模算法
5.2變治策略
5.2.1排序問題
5.2.2平衡查找樹
5.2.3霍納法則和二進制冪
5.2.4問題化簡
總結
習題5
第6章動態規劃
6.1概述
6.2算法特點
6.2.1備忘錄方法
6.2.2最最佳化原理
6.2.3求解步驟
6.3矩陣連乘問題
6.4最長公共子序列
6.501背包問題
6.6最大子段和
6.7最優二叉查找樹
總結
習題6
第7章時空權衡技術
7.1時空權衡策略
7.2計數排序
7.3字元串匹配
7.4散列法
總結
習題7
第8章貪心算法
8.1概述
8.1.1貪心算法的基本要素
8.1.2貪心算法的求解過程
8.2活動安排問題
8.3背包問題
8.4最小生成樹問題
8.4.1Prim算法
8.4.2Kruskal算法
8.5單源(點)最短路徑問題
8.6哈夫曼編碼
總結
習題8
第9章回溯法和分支限界法
9.1回溯法
9.1.1概述
9.1.2子集和問題
9.1.3n皇后問題
9.1.4哈密頓迴路
9.1.5裝載問題
9.2分支限界法
9.2.1概述
9.2.201背包問題
9.2.3任務分配問題
9.2.4多段圖的最短路徑問題
9.2.5旅行商問題
總結
習題9
第10章NP完全性理論
10.1判定問題和最最佳化問題
10.2P類問題
10.3NP類問題
10.4NP完全問題
10.5典型的NP完全問題
10.6其他NP完全問題
10.7NP完全問題的計算機處理
總結
習題10
第11章案例精選
11.1果園籬笆問題
11.2空中飛行管理問題
11.3去數問題
11.4極差問題
11.5最優合併問題
11.6在棋盤中實現從初始布局到目標布局的轉變
11.7商店購物問題
11.8旅遊預算問題
11.9防衛飛彈問題
11.10釣魚問題
11.11胖男孩問題
11.12護衛隊問題
參考文獻
