算法設計與分析

第1章  算法基礎  1  1.1  算法  1   1.1.1  冒泡排序  1   1.1.2  循環(huán)不變式和冒泡排序算法的#=正確性  2   1.1.3  偽代碼使用約定  3  1.2  算法分析  4   1.2.1  冒泡排序算法分析  5   1.2.2  最壞情況和平均情況分析  6   1.2.3  增長的數(shù)量級  6  1.3  算法的運行時間  7   1.3.1  函數(shù)增長  7   1.3.2  漸近表示  8  習題  10 第2章  分治法  13  2.1  遞歸與遞歸方程  13   2.1.1  遞歸的概念  13   2.1.2  替換方法  16   2.1.3  遞歸樹方法  17   2.1.4  主方法  18  2.2  分治法  20   2.2.1  分治法的基本思想  20   2.2.2  二叉查找算法  21  2.3  分治法應用實例  24   2.3.1  找最大值與最小值  24   2.3.2  Strassen矩陣乘法  26   2.3.3  整數(shù)相乘  27   2.3.4  歸并排序  28   2.3.5  快速排序  33   2.3.6  線性時間選擇  38   2.3.7  最近點對問題  42  習題  44 第3章  動態(tài)規(guī)劃  49  3.1  用表代替遞歸  49  3.2  01背包問題  52  3.3  矩陣鏈乘問題  54  3.4  動態(tài)規(guī)劃的基本元素  60  3.5  備忘錄方法  64  3.6  裝配線調度問題  70  3.7  最長公共子序列  73  3.8  最優(yōu)二分檢索樹  77  3.9  凸多邊形最優(yōu)三角剖分  84  習題  88 第4章  貪心法  98  4.1  背包問題  98  4.2  活動選擇問題   101  4.3  貪心算法的基本元素  105  4.4  哈夫曼編碼  107  4.5  最小生成樹算法  113   4.5.1  最小生成樹的基本原理  114   4.5.2  Kruskal算法  117   4.5.3  Prim算法  121   4.5.4  Boruvka算法  125   4.5.5  比較與改進  127  4.6  Dijkstra單源點最短路徑算法  127  4.7  貪心算法的理論基礎  133  4.8  作業(yè)調度問題  136  習題  138 第5章  回溯法  144  5.1  回溯法的基本原理  144  5.2  n皇后問題  148  5.3  子集和數(shù)問題  151  5.4  01背包問題  154  5.5  著色問題  157  習題  160 第6章  分枝限界法  163  6.1  分枝限界法的基本思想  163  6.2  01背包問題  167  6.3  作業(yè)調度問題  175  習題  178 第7章  NP完全性  180  7.1  P類問題與NP類問題  180   7.1.1  復雜類P和復雜類NP  181   7.1.2  NP中的有趣問題  183  7.2  NP完全性  185   7.2.1  多項式時間歸約和NP難度  185   7.2.2  Cook定理  186  7.3  典型的NP完全問題  187   7.3.1  CNF3SAT問題和3SAT問題  189   7.3.2  頂點覆蓋問題  191   7.3.3  團問題和集合覆蓋問題  193   7.3.4  子集和數(shù)問題與背包問題  194   7.3.5  哈密爾頓回路問題和TSP問題  196   習題  199 索引  201 參考文獻  206