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