算法設(shè)計(jì)與分析

第1章  算法基礎(chǔ)  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  增長(zhǎng)的數(shù)量級(jí)  6  1.3  算法的運(yùn)行時(shí)間  7   1.3.1  函數(shù)增長(zhǎng)  7   1.3.2  漸近表示  8  習(xí)題  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  分治法應(yīng)用實(shí)例  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  線性時(shí)間選擇  38   2.3.7  最近點(diǎn)對(duì)問題  42  習(xí)題  44 第3章  動(dòng)態(tài)規(guī)劃  49  3.1  用表代替遞歸  49  3.2  01背包問題  52  3.3  矩陣鏈乘問題  54  3.4  動(dòng)態(tài)規(guī)劃的基本元素  60  3.5  備忘錄方法  64  3.6  裝配線調(diào)度問題  70  3.7  最長(zhǎng)公共子序列  73  3.8  最優(yōu)二分檢索樹  77  3.9  凸多邊形最優(yōu)三角剖分  84  習(xí)題  88 第4章  貪心法  98  4.1  背包問題  98  4.2  活動(dòng)選擇問題   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  比較與改進(jìn)  127  4.6  Dijkstra單源點(diǎn)最短路徑算法  127  4.7  貪心算法的理論基礎(chǔ)  133  4.8  作業(yè)調(diào)度問題  136  習(xí)題  138 第5章  回溯法  144  5.1  回溯法的基本原理  144  5.2  n皇后問題  148  5.3  子集和數(shù)問題  151  5.4  01背包問題  154  5.5  著色問題  157  習(xí)題  160 第6章  分枝限界法  163  6.1  分枝限界法的基本思想  163  6.2  01背包問題  167  6.3  作業(yè)調(diào)度問題  175  習(xí)題  178 第7章  NP完全性  180  7.1  P類問題與NP類問題  180   7.1.1  復(fù)雜類P和復(fù)雜類NP  181   7.1.2  NP中的有趣問題  183  7.2  NP完全性  185   7.2.1  多項(xiàng)式時(shí)間歸約和NP難度  185   7.2.2  Cook定理  186  7.3  典型的NP完全問題  187   7.3.1  CNF3SAT問題和3SAT問題  189   7.3.2  頂點(diǎn)覆蓋問題  191   7.3.3  團(tuán)問題和集合覆蓋問題  193   7.3.4  子集和數(shù)問題與背包問題  194   7.3.5  哈密爾頓回路問題和TSP問題  196   習(xí)題  199 索引  201 參考文獻(xiàn)  206