算法設計（C++版）

目錄

第1章算法概述

1.1算法的基本概念

1.1.1學習算法的重要性

1.1.2算法的定義及特性

1.1.3算法的描述方式

1.2算法設計的一般過程

1.3算法分析

1.3.1算法分析的概念

1.3.2時間復雜性

1.3.3空間復雜性

1.3.4算法漸進復雜性

1.3.5算法復雜性的權衡考慮

1.4遞歸

1.4.1認知遞歸

1.4.2n的階乘

1.4.3排列問題

1.4.4最大公約數

1.4.5遞歸算法的復雜性分析

拓展知識： 算法界十大名師簡介

本章習題

第2章貪心算法

2.1貪心算法概述

2.1.1貪心算法的基本思想

2.1.2貪心算法的基本要素

2.1.3貪心算法的解題步驟及算法設計模式

2.2會場安排問題

2.3單源最短路徑問題

2.4哈夫曼編碼

2.5最小生成樹

2.5.1Prim算法

2.5.2Kruskal算法

2.5.3兩種算法的比較

拓展知識： 遺傳算法

本章習題

第3章分治算法

3.1分治算法概述

3.1.1分治算法的基本思想

3.1.2分治算法的解題步驟

3.2二分查找

3.3循環賽日程表

3.4合並排序

3.5快速排序

3.6最接近點對問題

拓展知識： 禁忌搜索算法

本章習題

第4章動態規劃算法

4.1動態規劃算法概述

4.1.1動態規劃算法的基本思想

4.1.2動態規劃算法的解題步驟

4.1.3動態規劃算法的基本要素

4.2矩陣連乘問題

4.3凸多邊形最優三角剖分問題

4.4最長公共子序列問題

4.5加工順序問題

4.601背包問題

4.7最優二叉查找樹

拓展知識： 模擬退火算法

本章習題

第5章回溯算法及分支限界算法

5.1回溯算法

5.1.1回溯算法的算法框架及思想

5.1.2子集樹

5.1.3排列樹

5.1.4滿m叉樹

5.2分支限界算法

5.2.1分支限界算法的基本思想

5.2.201背包問題

5.2.3旅行商問題

5.2.4布線問題

5.2.5分支限界算法與回溯算法的比較

拓展知識： 蟻群算法

本章習題

第6章隨機化算法

6.1隨機化算法概述

6.1.1隨機化算法的類型及特點

6.1.2隨機數發生器

6.2數值隨機化算法

6.2.1計算π值的問題及分析

6.2.2計算定積分

6.3蒙特卡洛算法

6.3.1主元素問題

6.3.2素數測試

6.4拉斯維加斯算法

6.4.1整數因子分解問題

6.4.2n皇後問題

6.5舍伍德算法

6.5.1隨機快速排序

6.5.2線性時間選擇問題

拓展知識： 粒子群優化算法

本章習題

第7章網絡流算法

7.1最大網絡流

7.1.1基本概念

7.1.2增廣路算法

7.1.3最大網絡流的變換與應用

7.2最小費用最大流

7.2.1基本概念

7.2.2消圈算法

7.2.3最小費用最大流的變換與應用

拓展知識： 捕食搜索算法

本章習題

第8章NP完全理論

8.1易解問題和難解問題

8.2P類問題和NP類問題

8.2.1P類問題

8.2.2NP類問題

8.2.3P類問題和NP類問題的關系

8.3NP完全問題

8.3.1多項式變換技術

8.3.2典型的NP完全問題

8.4NP完全問題的近似算法

8.4.1頂點覆蓋問題

8.4.2裝箱問題

8.4.3旅行商問題

8.4.4集合覆蓋問題

拓展知識： DNA計算

本章習題