第1 章 排序1
1.1 比較排序. 1
1.1.1 梳排序. 2
1.1.2 堆排序. 4
1.1.3 歸並排序 5
1.1.4 快速排序 8
1.1.5 內省排序 10
1.1.6 Timsort 11
1.2 非比較排序. 14
1.2.1 桶排序. 14
1.2.2 基數排序 15
1.3 總結 16
第2 章 哈希17
2.1 基本概念與實現.. 17
2.1.1 哈希函數 17
2.1.2 哈希錶. 19
2.2 哈希的應用. 20
2.2.1 相似性搜索.. 20
2.2.2 信息安全 23
2.2.3 比特幣. 25
2.2.4 負載均衡 26
第3 章 動態規劃與近似算法29
3.1 基本概念. 29
3.1.1 動態規劃 29
3.1.2 計算復雜性.. 30
3.2 字符串的編輯距離. 30
3.2.1 問題引入 31
3.2.2 動態規劃算法.. 33
3.2.3 滾動數組優化.. 35
3.2.4 上界限製 36
3.2.5 解的迴溯 37
3.2.6 分治算法 38
3.2.7 多個字符串的編輯距離. 41
3.3 子集和問題. 43
3.3.1 問題引入 43
3.3.2 子集和問題的動態規劃算法 43
3.3.3 最優化問題.. 44
3.3.4 滾動數組的技巧. 45
第4 章 高斯消去法59
4.1 問題引入. 59
4.2 矩陣編程基礎 60
4.3 三角方程組. 62
4.3.1 三角矩陣 62
4.3.2 三角矩陣的存儲. 63
4.3.3 三角方程組求解. 64
4.4 高斯消去法. 66
4.4.1 算法概述 66
4.4.2 高斯變換 68
4.4.3 LU 分解.. 69
4.4.4 Cholesky 分解.. 70
4.5 主元選擇. 71
4.5.1 列選主元 71
4.5.2 全選主元 73
4.5.3 主元與計算量.. 74
4.6 稀疏矩陣的編程基礎 75
4.6.1 稀疏嚮量 76
4.6.2 稀疏矩陣 79
4.7 稀疏LU 分解. 82
4.7.1 Markowitz 算法.. 82
4.7.2 最小度算法.. 83
第5 章 圖論與綫性規劃86
5.1 綫性規劃基礎 86
5.1.1 Fourier Motzkin 消去法. 89
5.1.2 基 91
5.1.3 單純形方法.. 93
5.1.4 對偶.. 95
5.2 全單模矩陣. 98
5.2.1 關聯矩陣 98
5.2.2 全單模矩陣.. 99
5.2.3 全單模矩陣與圖論 100
5.2.4 全單模矩陣與綫性規劃. 103
5.3 圖論中的經典問題. 104
5.3.1 單源最短路問題. 104
5.3.2 二分圖的最大匹配與最小覆蓋問題 106
5.3.3 最大流與最小割問題.. 108
5.4 延伸閱讀. 109
5.4.1 逐步綫性規劃.. 109
5.4.2 半正定規劃.. 111
第6 章 無約束優化113
6.1 單峰函數的最值.. 114
6.1.1 三分法. 115
6.1.2 對分法. 115
6.1.3 黃金分割法.. 116
6.1.4 小結.. 117
6.2 無導數優化方法.. 118
6.2.1 模式搜索法.. 118
6.2.2 坐標下降法.. 119
6.2.3 代理模型法.. 120
6.3 導數優化方法 121
6.3.1 綫搜索. 122
6.3.2 梯度下降法.. 123
6.3.3 共軛梯度法.. 124
6.3.4 牛頓法. 127
6.3.5 擬牛頓法 128
6.4 最小二乘. 132
6.4.1 綫性最小二乘.. 133
6.4.2 非綫性最小二乘. 133
第7 章 迭代法136
7.1 綫性方程組的迭代法 136
7.1.1 一階定常格式迭代法.. 136
7.1.2 Krylov 子空間算法 142
7.1.3 無約束優化方法. 147
7.2 非綫性方程組的迭代法 147
7.2.1 不動點迭代.. 148
7.2.2 Newton-Raphson 迭代. 149
7.2.3 無約束優化方法. 152
第8 章 插值與擬閤153
8.1 插值 153
8.1.1 常見的插值算法. 154
8.1.2 插值的應用.. 158
8.2 擬閤 163
8.2.1 常見的擬閤算法. 164
8.2.2 擬閤的應用.. 166
參考文獻169
· · · · · · (收起)