目 录

第1篇

常用算法的原理、实现与优化

第1章 算法分析与设计基础 ...................................002

1.1 基本概念 ...................................................002

1.2 算法复杂度指标 ..............................................003

1.2.1 时间复杂度 ...........................................003

1.2.2 测量程序运行时间和空间使用情况 ........................005

1.3 算法优化常用思路 ............................................008

1.3.1 算法层面优化 .........................................008

1.3.2 代码层面优化 .........................................010

习题 ............................................................013

第2章 枚举算法 ............................................017

2.1 数学类问题算法设计与应用 .....................................017

2.2 其他类问题算法设计与应用 .....................................031

习题 ............................................................037

第3章 解析算法 ............................................039

3.1 数学类问题算法设计与应用 .....................................039

3.2 物理类问题算法设计与应用 .....................................048

3.3 其他类问题算法设计与应用 .....................................053

习题 ............................................................061

第4章 递推与迭代算法 ......................................063

4.1 数学类问题算法设计与应用 .....................................063

4.2 其他类问题算法设计与应用 .....................................085

习题 ............................................................098

第5章 递归与回溯算法 ......................................101

5.1 数学类问题算法设计与应用 .....................................102

5.2 其他类问题算法设计与应用 .....................................105

5.3 尾递归优化 .................................................120

习题 ............................................................122

第6章 排序算法 ............................................124

6.1 排序算法的原理与实现 ........................................124

6.1.1 冒泡排序算法 .........................................124

6.1.2 选择排序算法 .........................................126

6.1.3 插入排序算法 .........................................128

6.1.4 侏儒排序算法 .........................................129

6.1.5 希尔排序算法 .........................................129

6.1.6 堆排序算法 ...........................................130

6.1.7 归并排序算法 .........................................131

6.1.8 快速排序算法 .........................................133

6.1.9 基数排序算法 .........................................134

6.1.10 计数排序算法 ........................................135

6.2 排序算法高级应用 ............................................138

习题 ............................................................147

第7章 查找算法 ............................................150

7.1 线性查找算法 ................................................150

7.2 二分法查找 .................................................159

习题 ............................................................162

第8章 贪心算法 ............................................164

8.1 找零钱问题 .................................................164

8.2 幼儿园加餐吃面包问题 ........................................165

8.3 汽车加油问题 ................................................166

8.4 区间合并问题 ................................................167

8.5 分数分解问题 ................................................167

8.6 若干数字中前后元素最大差问题 .................................169

8.7 活动安排问题 ................................................169

8.8 哈夫曼编码与解码 ............................................171

习题 ............................................................174

第9章 分治法 ..............................................176

9.1 方程近似根 .................................................176

9.2 任意数列的逆序数 ............................................177

9.3 大自然数相乘 ................................................180

9.4 若干整数的第k大元素 ........................................181

9.5 元素之和最大的连续子序列 .....................................186

9.6 二维平面距离最近的两个点 .....................................188

习题 ............................................................192

第10章 动态规划算法 .......................................193

10.1 斐波那契数列第n个数 .......................................194

10.2 找零钱问题 ................................................194

10.3 奖品收集问题 ...............................................197

10.4 0-1背包问题 ...............................................200

10.5 最长非递减子序列 ...........................................206

10.6 最长公共子序列 .............................................210

习题 ............................................................214

第2篇

算法在不同学科中的应用

第11章 数论算法 ...........................................216

11.1 进制转换 ..................................................216

11.2 最大公约数 ................................................217

11.3 素性检测 ..................................................219

11.4 大数乘法与多项式乘法 .......................................229

11.5 乘模逆、扩展欧几里得算法 ....................................234

11.6 中国剩余定理 ...............................................237

11.7 快速幂模算法 ...............................................239

11.8 水仙花数 ..................................................244

11.9 平方数与自守数 .............................................249

11.10 整数分解 .................................................251

习题 ............................................................259

第12章 线性代数算法 .......................................261

12.1 向量基本运算 ...............................................261

12.2 矩阵基本运算 ...............................................265

12.3 矩阵行列式、代数余子式、逆矩阵 ..............................269

习题 ............................................................275

第13章 概率论与随机过程算法 ................................277

13.1 概率论的基本概念 ...........................................277

13.2 算法应用案例解析 ...........................................279

习题 ............................................................288

第14章 益智游戏类算法 .....................................289

14.1 24点游戏 ..................................................289

14.2 蒙蒂霍尔悖论游戏 ...........................................290

14.3 寻宝游戏 ..................................................292

14.4 模拟发红包 ................................................297

14.5 聪明的尼姆游戏 .............................................298

14.6 抓狐狸游戏 ................................................299

14.7 确定旅游目的地 .............................................301

14.8 制作漂亮手链 ...............................................303

14.9 数字可达游戏 ...............................................304

14.10 电影院选座位问题 ..........................................307

14.11 数独游戏盘面生成与自动求解 .................................308

14.12 推理游戏 .................................................313

14.13 迷宫自动寻找最短路径 ......................................315

习题 ............................................................318

第15章 图论算法 ...........................................320

15.1 图的概念、表示、应用与可视化 ................................320

15.1.1 基本概念与应用场景 .................................320

15.1.2 图的表示方式 .......................................321

15.1.3 图的可视化 .........................................325

15.1.4 寻找人群中的明星 ...................................326

15.2 二叉树与多叉树节点遍历 ......................................326

15.3 通路、回路、最短路径 .......................................331

15.4 拓扑排序 ..................................................340

15.5 图着色问题 ................................................341

15.6 最小生成树 ................................................344

15.7 完美匹配 ..................................................346

15.8 最大流 ....................................................347

习题 ............................................................352

第16章 机器学习算法 .......................................353

16.1 线性回归算法原理与应用 ......................................353

16.1.1 线性回归算法原理 ...................................353

16.1.2 使用线性回归模型预测儿童身高 ........................355

16.2 协同过滤算法原理与电影推荐 ..................................357

16.3 朴素贝叶斯算法原理与应用 ....................................358

16.3.1 分类算法基本原理 ...................................358

16.3.2 使用朴素贝叶斯算法进行垃圾邮件分类 ...................359

16.4 分类算法与聚类算法 .........................................363

16.4.1 使用KNN算法判断交通工具类型 ........................363

16.4.2 使用K-Means算法压缩图像颜色 ........................365

16.4.3 DBSCAN算法原理与应用 ..............................368

16.5 关联规则分析算法原理与应用 ..................................370

16.5.1 基本概念与算法原理 .................................371

16.5.2 使用关联规则分析算法分析和预测演员关系 ...............371

习题 ............................................................375

第17章 计算机图形学算法 ....................................376

17.1 Bresenham直线生成算法 .....................................376

17.2 二维平面直线裁剪算法 .......................................379

17.2.1 Cohen-Sutherland裁剪算法 ..........................380

17.2.2 Liang-BarSky裁剪算法 ..............................384

17.3 求解点集的凸包 .............................................388

习题 ............................................................392

第18章 密码学算法 .........................................394

18.1 安全哈希算法 ...............................................394

18.2 对称密钥密码算法DES和AES ..................................395

18.3 非对称密钥密码算法RSA与数字签名算法DSA .....................397

18.3.1 RSA算法 ...........................................397

18.3.2 DSA算法 ...........................................400

习题 ............................................................401

参考文献 ...................................................402