| 作者 |
| （美）Robert Sedgewick（罗伯特·塞奇威克） （法）Philippe Flajolet（费利佩·弗拉若莱） |
| 丛书名 |
| 出版社 |
| 电子工业出版社 |
| ISBN |
| 9787121353680 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 本书全面介绍了算法的数学分析所涉及的主要技术。涵盖的内容来自经典的数学课题（包括离散 数学、初等实分析、组合数学），以及经典的计算机科学课题（包括算法和数据结构）。本书的重点是“平均情况”或“概率性”分析，书中也论述了“最差情况”或“复杂性”分析所需的基本数学工具。本书第1 版为行业代表性著作，第2 版不仅对书中图片和代码进行了更新，还补充了新章节。全书共9 章，第1 章是导论；第2～5 章介绍数学方法；第6～9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外，本书特设配套免费学习网站，为读者提供了很多关于算法分析的补充材料，包括课件和相关网站的链接，帮助读者提高学习兴趣，完成更深入的学习。 |
| 目录 |
| 第 1章算法分析 ............... 1 1.1 为什么要做算法分析 ..........................................................1 1.2 算法理论 ..................3 1.3 算法分析概述 ..........8 1.4 平均情况分析 ........10 1.5 实例：快速排序算法的分析 ............................................12 1.6 渐近近似 ................ 18 1.7 分布 ........................ 20 1.8 随机算法 ................ 22 参考文献 ......................... 25 第 2章递归关系 ............. 28 2.1 基本性质 ................ 29 2.2 一阶递归 ................ 33 2.3 一阶非线性递归 ....35 2.4 高阶递归 ................ 38 2.5 求解递归的方法 ....42 2.6 二分分治递归和二进制数 ................................................49 2.7 一般的分治递归 ....57 参考文献 ......................... 62 第 3章母函数 .................. 64 3.1 普通型母函数 ........65 算法分析导论（第 2版） 3.2 指数型母函数 .........69 3.3 利用母函数求解递归 ........................................................72 3.4 母函数的展开 .........79 3.5 利用母函数进行变换 ........................................................82 3.6 关于母函数的函数方程 ....................................................84 3.7 利用 OGF求解三项中值 Quicksort递归.........................87 3.8 利用母函数计数 .....89 3.9 概率母函数 .............93 3.10 双变量母函数 .......96 3.11特殊函数.............101 参考文献........................107 第 4章渐近逼近 ........... 109 4.1 渐近逼近的概念 ...111 4.2 渐近展开式 ...........116 4.3 处理渐近展开式 ...123 4.4 有限和的渐近逼近 ..........................................................129 4.5 欧拉-麦克劳林求和 ........................................................131 4.6 二元渐近...............137 4.7 拉普拉斯方法 .......149 4.8 算法分析中的“正态”举例 ..........................................152 4.9 算法分析中的“泊松”举例 ..........................................155 参考文献........................159 第 5章分析组合 ........... 161 5.1 正式的基础 ...........162 5.2 无标记类的符号方法 ......................................................163 5.3 有标记类的符号方法 ......................................................169 5.4 参数的符号方法 ...177 5.5 母函数系数逼近 ...182 参考文献........................188 第 6章树........................ 189 6.1 二叉树...................190 XV 6.2 森林和树 .............. 192 6.3 树和二叉树的组合等价 ..................................................194 6.4 树的性质 .............. 200 6.5 树算法的例子 ......204 6.6 二叉搜索树 .......... 207 6.7 随机 Catalan树 .... 211 6.8 二叉搜索树中的路径长度 .............................................. 216 6.9 随机树的附加参数 .........................................................219 6.10 高度 .................... 223 6.11树属性在平均情况下的结果总结 ................................229 6.12 拉格朗日反演 ....230 6.13 无序树 ................ 233 6.14 标记树 ................ 242 6.15 其他类型的树 ....245 参考文献 ....................... 253 第 7章排列 ....................256 7.1 排列的基本性质 .. 257 7.2 排列算法 .............. 263 7.3 排列的表示法 ......266 7.4 计数问题 .............. 271 7.5 通过 CGF分析排列的性质............................................275 7.6 逆序和插入排序 .. 285 7.7 从左到右最小值和选择排序 ..........................................291 7.8 环与原地排列 ......297 7.9 极值参数 .............. 300 参考文献 ....................... 304 第 8章字符串与字典树 .........................................................306 8.1 字符串搜索 .......... 307 8.2 位串的组合性质 .. 310 8.3 正则表达式 .......... 320 8.4 有穷状态自动机和 KMP算法 .......................................323 8.5 上下文无关的语法 .........................................................326 算法分析导论（第 2版） 8.6 字典树...................332 8.7 字典树算法 ...........336 8.8 字典树的组合性质 ..........................................................340 8.9 更大的字符表 .......345 参考文献........................347 第 9章单词与映射 ...... 350 9.1 使用分离链接的散列 ......................................................351 9.2 球与瓮的模型和单词的性质 ..........................................353 9.3 生日悖论与优惠券收集者问题 ......................................360 9.4 占据限制与极值参数 ......................................................367 9.5 占据分布...............372 9.6 开放寻址散列法 ...379 9.7 映射.......................386 9.8 整数因子分解与映射 ......................................................396 参考文献........................401 |