那不勒坦著的《算法基礎(第5版)》通過大量示
例介紹了算法設計、算法的復雜度分析以及計算復雜
度。主要內容有：算法設計與分析、分而治之方法、
動態規劃方法、貪婪方法、回溯算法、分支定界算法
、計算復雜度、難解性NP理論、遺傳算法和遺傳編程
、數論算法、並行算法等。此外，本書在每章末尾都
提供了大量練習，而且還提供了全面的教輔材料及答
案，是教授和學
本書適合高等院校學生、程序員及算法分析和設
計人員。

第1章 算法：效率、分析和階
1.1 算法
1.2 開發高效算法的重要性
1.2.1 順序查找與二分查找的對比
1.2.2 斐波那契序列
1.3 算法分析
1.3.1 復雜度分析
1.3.2 理論應用
1.3.3 正確性分析
1.4 階
1.4.1 階的直觀介紹
1.4.2 階數的嚴謹介紹
1.4.3 利用極限計算階
1.5 本書概要
1.6 習題
第2章 分而治之
2.1 二分查找
2.2 合並排序
2.3 分而治之方法
2.4 快速排序（分割交換排序）
2.5 Strassen矩陣乘法算法
2.6 大整數的算術運算
2.6.1 大整數的表示：加法和其他線性時間運算
2.6.2 大整數的乘法
2.7 確定閾值
2.8 不應使用分而治之方法的情況
2.9 習題
第3章 動態規劃
3.1 二項式繫數
3.2 Floyd短路徑算法
3.3 動態規劃與優化問題
3.4 矩陣鏈乘法
3.5 優二叉查找樹
3.6 旅行推銷員問題
3.7 序列對準
3.8 習題
第4章 貪婪方法
4.1 小生成樹
4.1.1 Prim算法
4.1.2 Kruskal算法
4.1.3 Prim算法與Kruskal算法的比較
4.1.4 終討論
4.2 單源短路徑的Dijkstra算法
4.3 調度計劃
4.3.1 使繫統內總時間短
4.3.2 帶有終期限的調度安排
4.4 霍夫曼編碼
4.4.1 前綴碼
4.4.2 霍夫曼算法
4.5 貪婪方法與動態規劃的比較：背包問題
4.5.1 0-1背包問題的一種貪婪方法
4.5.2 部分背包問題的貪婪方法
4.5.3 0-1背包問題的動態規劃方法
4.5.4 0-1背包問題動態規劃算法的改進
4.6 習題
第5章 回溯
5.1 回溯方法
5.2 n皇後問題
5.3 用蒙特卡洛算法估計回溯算法的效率
5.4 “子集之和”問題
5.5 圖的著色
5.6 哈密頓回路問題
5.7 0-1背包問題
5.7.1 0-1背包問題的回溯算法
5.7.2 比較0-1背包問題的動態規劃算法與回溯算法
5.8 習題
第6章 分支定界
6.1 用0-1背包問題說明分支定界
6.1.1 帶有分支定界修剪的寬度優先查找
6.1.2 帶有分支定界修剪的佳優先查找
6.2 旅行推銷員問題
6.3 溯因推理（診斷）
6.4 習題
第7章 計算復雜度介紹：排序問題
7.1 計算復雜度
7.2 插入排序和選擇排序
7.3 每次比較多減少一個倒置的算法的下限
7.4 再談合並排序
7.5 再談快速排序
7.6 堆排序
7.6.1 堆和基本堆例程
7.6.2 堆排序的一種實現
7.7 合並排序、快速排序和堆排序的比較
7.8 僅通過鍵的比較進行排序的下限
7.8.1 排序算法的決策樹
7.8.2 差情況下的下限
7.8.3 平均情況下的下限
7.9 分配排序（基數排序）
7.10 習題
第8章 再談計算復雜度：查找問題
8.1 僅通過鍵的比較進行查找的下限
8.1.1 差表現的下限
8.1.2 平均情況下的下限
8.2 插值查找
8.3 樹中的查找
8.3.1 二叉查找樹
8.3.2 B樹
8.4 散列
8.5 選擇問題：對手論證
8.5.1 找出大鍵
8.5.2 同時找出大鍵和小鍵
8.5.3 找出第二大的鍵
8.5.4 查找第k小的鍵
8.5.5 選擇問題的一種概率算法
8.6 習題
第9章 計算復雜度和難解性：NP理論簡介
9.1 難解性
9.2 再談輸入規模
9.3 三類一般問題
9.3.1 已經找到多項式時間算法的問題
9.3.2 已經證明難解的問題
9.3.3 未被證明是難解的，但也從來沒有找到多項式時間算法的問題
9.4 NP理論
9.4.1 集合P和
9.4.2 NP**問題
9.4.3 NP困難、NP容易和NP等價問題
9.5 處理NP困難問題
9.5.1 旅行推銷員問題的近似算法
9.5.2 裝箱問題的近似算法
9.6 習題
**0章 遺傳算法和遺傳編程
10.1 遺傳知識復習
10.2 遺傳算法
10.2.1 算法
10.2.2 說明範例
10.2.3 旅行推銷員問題
10.3 遺傳編程
10.3.1 說明範例
10.3.2 人造螞蟻
10.3.3 在金融貿易中的應用
10.4 討論及擴展閱讀
10.5 習題
**1章 數論算法
11.1 數論回顧
11.1.1 合數與質數
11.1.2 大公約數
11.1.3 質因數分解
11.1.4 小公倍數
11.2 計算大公約數
11.2.1 歐氏算法
11.2.2 歐氏算法的擴展
11.3 模運算回顧
11.3.1 群論
11.3.2 關於n同餘
11.3.3 子群
11.4 模線性方程的求解
11.5 計算模的冪
11.6 尋找大質數
11.6.1 尋找大質數
11.6.2 檢查一個數字是否為質數
11.7 RSA公鑰密碼繫統
11.7.1 公鑰加密繫統
11.7.2 RSA加密繫統
11.8 習題
**2章 並行算法簡介
12.1 並行體繫結構
12.1.1 控制機制
12.1.2 地址空間的組織
12.1.3 互聯網絡
12.2 PRAM模型
12.2.1 為CREWPRAM模型設計算法
12.2.2 為CRCWPRAM模型設計算法
12.3 習題
附錄A**數學知識回顧
附錄B求解遞歸方程：在遞歸算法分析
中的應用
附錄C不交集的數據結構
參考文獻