算法設計與分析（第2版·Python版）

目錄

 

 

第1章算法概述

 

1.1什麼是算法

 

1.2為什麼學習算法

 

1.3算法的描述方式

 

1.4算法設計的一般過程

 

1.5算法分析

 

1.5.1算法分析的概念

 

1.5.2時間復雜度和空間復雜度

 

1.5.3漸近復雜性態

 

1.5.4漸近意義下的記號

 

1.5.5算法的運行時間T(n)建立的依據

 

1.5.6算法所占用的空間S(n)建立的依據

 

1.6遞推方程求解方法

 

1.6.1疊代法

 

1.6.2遞歸樹

 

1.6.3差消法

 

1.6.4主方法

 

第2章貪心算法——貪心不足

 

2.1概述

 

2.1.1貪心算法的本質

 

2.1.2貪心算法的基本要素

 

2.2活動安排問題

 

2.2.1問題分析——貪心策略

 

2.2.2算法設計

 

2.2.3實例構造

 

2.2.4算法分析

 

2.2.5Python實踐

 

 

 

2.3單源最短路徑問題

 

2.3.1問題分析——貪心策略

 

2.3.2算法設計

 

2.3.3實例構造

 

2.3.4算法分析

 

2.3.5Python實踐

 

 

目錄

 

 

2.4哈夫曼編碼

 

2.4.1問題分析——貪心策略

 

2.4.2算法設計

 

2.4.3實例構造

 

2.4.4算法分析

 

2.4.5Python實踐

 

2.5最小生成樹——Prim算法

 

2.5.1問題分析——貪心策略

 

2.5.2算法設計

 

2.5.3實例構造

 

2.5.4算法分析

 

2.5.5Python實踐

 

2.6最小生成樹——Kruskal算法

 

2.6.1問題分析——貪心策略

 

2.6.2算法設計

 

2.6.3實例構造

 

2.6.4算法分析

 

2.6.5Python實踐

 

2.7背包問題

 

2.7.1問題分析——貪心策略

 

2.7.2算法設計

 

2.7.3實例構造

 

2.7.4算法分析

 

2.7.5Python實踐

 

第3章分治算法——分而治之

 

3.1概述

 

3.1.1分治算法的本質

 

3.1.2分治算法的求解步驟

 

3.2二分查找

 

3.2.1問題分析——分與治的方法

 

3.2.2算法設計

 

3.2.3實例構造

 

3.2.4算法分析

 

3.2.5Python實踐

 

3.3選第二大元素

 

3.3.1問題分析——分與治的方法

 

3.3.2算法設計

 

3.3.3實例構造

 

3.3.4算法分析

 

3.3.5Python實踐

 

3.4循環賽日程表

 

3.4.1問題分析——分與治的方法

 

3.4.2算法設計

 

3.4.3實例構造

 

3.4.4算法分析

 

3.4.5Python實踐

 

 

3.5合並排序

 

3.5.1問題分析——分與治的方法

 

3.5.2算法設計

 

3.5.3實例構造

 

3.5.4算法分析

 

3.5.5Python實踐

 

3.6快速排序

 

3.6.1問題分析——分與治的方法

 

3.6.2算法設計

 

3.6.3實例構造

 

3.6.4算法分析

 

3.6.5Python實踐

 

3.7線性時間選擇——找第k小問題

 

3.7.1問題分析——分與治的方法

 

3.7.2算法設計

 

3.7.3實例構造

 

3.7.4算法分析

 

3.7.5Python實踐

 

第4章動態規劃

 

4.1概述

 

4.1.1動態規劃的基本思想

 

4.1.2動態規劃的求解步驟

 

4.1.3動態規劃的基本要素

 

4.2矩陣連乘問題

 

4.2.1問題分析——遞歸關系

 

4.2.2算法設計

 

4.2.3實例構造

 

4.2.4算法分析

 

4.2.5Python實踐

 

4.3凸多邊形最優三角剖分

 

4.3.1問題分析——遞歸關系

 

4.3.2算法設計

 

4.3.3實例構造

 

4.3.4算法分析

 

4.3.5Python實踐

 

 

4.4最長公共子序列問題

 

4.4.1問題分析——遞歸關系

 

4.4.2算法設計

 

4.4.3實例構造

 

4.4.4算法分析

 

4.4.5Python實踐

 

4.5加工順序問題

 

4.5.1問題分析——遞歸關系

 

4.5.2算法設計

 

4.5.3實例構造

 

4.5.4算法分析

 

4.5.5Python實踐

 

4.601背包問題

 

4.6.1問題分析——遞歸關系

 

4.6.2算法設計

 

4.6.3實例構造

 

4.6.4算法分析

 

4.6.5算法的改進

 

4.6.6Python實踐

 

4.7最優二叉查找樹

 

4.7.1問題分析——遞歸關系

 

4.7.2算法設計

 

4.7.3實例構造

 

4.7.4算法分析

 

4.7.5Python實踐

 

第5章回溯法——深度優先搜索

 

5.1概述

 

5.2典型的解空間結構

 

5.2.1子集樹

 

5.2.2排列樹

 

5.2.3滿m叉樹

 

5.301背包問題——子集樹

 

5.3.1問題分析——解空間及搜索條件

 

5.3.2算法設計

 

5.3.3實例構造

 

5.3.4算法的改進

 

5.3.5算法分析

 

5.3.6Python實踐

 

5.4最大團問題——子集樹

 

5.4.1問題分析——解空間及搜索條件

 

5.4.2算法設計

 

5.4.3實例構造

 

5.4.4算法分析

 

5.4.5Python實踐

 

5.5批處理作業調度問題——排列樹

 

5.5.1問題分析——解空間及搜索條件

 

5.5.2算法設計

 

5.5.3實例構造

 

5.5.4算法分析

 

5.5.5Python實踐

 

 

5.6旅行商問題——排列樹

 

5.6.1問題分析——解空間及搜索條件

 

5.6.2算法設計

 

5.6.3實例構造

 

5.6.4算法分析

 

5.6.5Python實踐

 

5.7圖的m著色問題——滿m叉樹

 

5.7.1問題分析——解空間及搜索條件

 

5.7.2算法設計

 

5.7.3實例構造

 

5.7.4算法分析

 

5.7.5Python實踐

 

5.8最小質量機器設計問題——滿m叉樹

 

5.8.1問題分析——解空間及搜索條件

 

5.8.2算法設計

 

5.8.3實例構造

 

5.8.4算法分析

 

5.8.5Python實踐

 

 

第6章分支限界法——寬度優先或最小耗費(最大效益)

優先搜索

 

6.1分支限界法的基本思想

 

6.201背包問題

 

6.3旅行商問題

 

6.4布線問題

 

6.4.1問題分析——解空間及搜索條件

 

6.4.2算法設計

 

6.4.3實例構造

 

6.4.4算法分析

 

6.4.5Python實踐

 

6.5分支限界法與回溯法的比較

 

 

第7章線性規劃問題與網絡流

 

7.1線性規劃問題

 

7.1.1一般線性規劃問題的描述

 

7.1.2標準型線性規劃問題的描述

 

7.1.3標準型線性規劃問題的單純形算法

 

7.2最大網絡流

 

7.2.1基本概念

 

7.2.2增廣路算法

 

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

 

7.3最小費用最大流

 

7.3.1基本概念

 

7.3.2消圈算法

 

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

 

第8章隨機化算法

 

8.1概述

 

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

 

8.1.2隨機數發生器

 

8.2數值隨機化算法

 

8.2.1計算π的值

 

8.2.2計算定積分

 

8.3蒙特卡洛算法

 

8.3.1主元素問題

 

8.3.2素數測試

 

8.4拉斯維加斯算法

 

8.4.1整數因子分解

 

8.4.2n皇後問題

 

8.5舍伍德算法

 

8.5.1隨機快速排序

 

8.5.2線性時間選擇

 

第9章NP完全理論

 

9.1易解問題和難解問題

 

9.2P類和NP類問題

 

9.2.1P類問題

 

9.2.2NP類問題

 

9.3NP完全問題

 

9.3.1多項式變換技術

 

9.3.2典型的NP完全問題

 

9.4NP完全問題的近似算法

 

9.4.1頂點覆蓋問題

 

9.4.2裝箱問題

 

9.4.3旅行商問題

 

9.4.4集合覆蓋問題

 

參考文獻