**部分 基礎知識 第1章 算法設計的基礎 1 1.1 算法的基本概念 1 1.1.1 算法的定義和特征 1 1.1.2 算法設計實例 3 1.2 算法的偽代碼描述 6 1.2.1 偽代碼的定義 6 1.2.2 算法的偽代碼實例描述 6 1.3 算法復雜度分析 7 1.3.1 時間復雜度分析 7 1.3.2 空間復雜度分析 10 1.4 學習和研究算法的原因 12 1.4.1 算法在問題求解中的地位 13 1.4.2 算法訓練能夠提高計算思維能力 15 1.4.3 算法設計的基本步驟 16 習題1 17 第2章 算法的數學基礎 19 2.1 常用的函數和公式 19 2.1.1 整數函數 19 2.1.2 對數函數 20 2.1.3 排列、組合和二項式系數 20 2.1.4 級數求和 21 2.2 求解遞歸方程 22 2.2.1 用特征方程求解遞歸方程 22 2.2.2 用遞歸樹方法求解遞歸方程 25 2.3 用遞推方法求解遞歸方程 26 2.3.1 遞推 26 2.3.2 用遞推法求解變系數遞歸方程 27 2.3.3 換名 28 習題2 30 第3章 排序問題的操作 33 3.1 基于堆的排序 33 3.1.1 堆的定義 33 3.1.2 堆的操作 34 3.1.3 堆的建立 38 3.1.4 堆的排序 40 3.2 基數排序 41 3.2.1 基數排序算法的思想方法 41 3.2.2 基數排序算法的實現 43 3.2.3 基數排序算法的分析 45 3.3 合并排序 46 3.3.1 合并排序算法的實現 46 3.3.2 合并排序算法的分析 48 3.4 選擇排序 49 3.5 起泡排序 50 習題3 51 第二部分 基本算法設計 第4章 遞歸與分治 53 4.1 基于歸納的遞歸算法 53 4.1.1 歸納的設計思想 53 4.1.2 遞歸算法的示例分析 54 4.1.3 遞歸在排列中的應用 56 4.1.4 整數劃分問題 57 4.2 分治法 59 4.2.1 分治法的設計思想 59 4.2.2 快速排序和歸并排序的分析 60 4.2.3 多項式乘積的分治算法 65 4.2.4 平面點集的*接近點對問題 68 4.2.5 棋盤覆蓋問題 73 習題4 76 第5章 貪婪法 77 5.1 貪婪法的設計思想 77 5.2 背包問題 78 5.2.1 背包問題貪婪法的實現 79 5.2.2 背包問題貪婪法的分析 80 5.3 *小生成樹問題 81 5.3.1 *小生成樹引言 81 5.3.2 克魯斯卡爾算法 82 5.3.3 普里姆算法 87 5.4 *短路徑問題 90 5.4.1 解*短路徑的狄斯奎諾算法 91 5.4.2 狄斯奎諾算法的實現與分析 92 5.5 圖的著色問題 94 習題5 96 第6章 動態規劃 98 6.1 動態規劃的示例——貨郎擔問題 98 6.2 多段圖的動態規劃法 100 6.2.1 多段圖的*短路徑問題 100 6.2.2 多源點*短路徑問題 103 6.3 *長公共子序列問題 105 6.3.1 *長公共子序列的搜索問題 105 6.3.2 *長遞增子序列問題 108 6.4 資源分配問題 110 6.4.1 資源分配策略 110 6.4.2 資源分配算法的實現 113 6.5 0/1背包問題 115 6.6 查找問題中的*優二叉查找樹 118 習題6 120 第三部分 基于搜索的算法設計 第7章 回溯法 122 7.1 回溯法的設計思想 122 7.1.1 問題的解空間 122 7.1.2 回溯法的設計思想 123 7.2 圖的回溯法 124 7.2.1 圖的著色問題的求解 124 7.2.2 哈密爾頓回路的求解 128 7.3 n后問題 130 7.3.1 4后問題的求解 130 7.3.2 8后問題的求解 131 7.4 批處理作業調度問題 133 習題7 134 第8章 分支與限界 136 8.1 分支與限界的設計思想 136 8.2 0/1背包問題 137 8.3 *大團問題 139 8.4 貨郎擔問題 140 8.5 圓排列問題 141 8.6 連續郵資問題 144 習題8 145 第四部分 算法的限制 第9章 隨機算法 147 9.1 隨機算法的設計思想 147 9.2 舍伍德隨機算法 148 9.2.1 隨機快速排序 149 9.2.2 隨機選擇算法 150 9.3 拉斯維加斯算法 152 9.3.1 8后問題 152 9.3.2 整數因子問題 153 9.4 蒙特卡羅算法 155 9.4.1 主元素問題 155 9.4.2 素數測試問題 157 習題9 159 第10章 NP完全問題與近似算法 161 10.1 P類和NP類問題 161 10.1.1 P類問題 161 10.1.2 NP類問題 162 10.2 NP完全問題 163 10.2.1 NP完全問題的定義 164 10.2.2 典型的NP完全問題 165 10.2.3 NP問題的求解 171 10.3 近似算法概述 171 10.3.1 近似算法的設計思想 171 10.3.2 近似算法的性能 172 10.4 圖中的近似問題 173 10.4.1 頂點覆蓋 173 10.4.2 *短路徑問題 175 10.5 多項式的近似求解 177 10.5.1 0/1背包問題的多項式 近似方案求解 177 10.5.2 子集求和問題的完全多項式 近似方案求解 180 習題10 182 第11章 專用算法設計技術 184 11.1 數據壓縮算法 184 11.1.1 數據壓縮概述 184 11.1.2 無損壓縮算法 186 11.1.3 有損壓縮算法 193 11.2 數據加密算法 199 11.2.1 數據加密概述 200 11.2.2 傳統加密算法 200 11.2.3 非對稱加密算法 205 11.3 遺傳算法 208 11.3.1 遺傳算法概述 208 11.3.2 遺傳算法 215 11.3.3 TSP問題 215 習題11 222 參考文獻 223