算法分析导论

图书标准信息

• 作者 [美]塞奇威克、[法]弗拉吉莱特 著；冯舜玺 译
• 出版社 机械工业出版社
• 出版时间 2006-04
• 版次 1
• ISBN 9787111164418
• 定价 38.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 314页
• 原版书名 An Introduction to the Analysis of Algorithms
• 丛书 计算机科学丛书

【内容简介】

本书全面介绍了算法的数学分析中使用的基本方法，所涉及的内容来自经典的数学课题（包括离散数学、初等实分析、组合数学），以及经典的计算机科学课题（包括算法和数据结构）。虽然书中论述了“最坏情形”和“复杂性”分析所需的基本数学工具，但是重点还是讨论“平均情形”或“概率”分析。论题涉及递归、生成函数、渐近性、树、串、映射等内容，以及对排序、树查找、串查找和散列诸算法的分析。
本书阐述了用于算法数学分析的主要方法，所涉及的材料来自经典数学课题，包括离散数学、初等实分析、组合数学，以及来自经典的计算机科学课题，包括算法和数据结构。本书内容集中覆盖基础、重要和有趣的算法，前面侧重数学，后面集中讨论算法分析的应用，重点是算法分析的数学方法。每章包含大量习题以及参考文献，使读者可以更深入地理解书中的内容。
本书适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材，也可供相关技术人员参考。

【作者简介】

RobertSedgewick，斯坦福大学博士（导师为DondldE.Knuth），普林斯顿大学计算机科学系dobeSystems公司董事，曾是XeroxPARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA。

【目录】

出版者的话
专家指导委员会
译者序
序
前言
记号解释
第1章算法分析概述
1.1为什么要对算法进行分析
1.2计算复杂性
1.3算法分析的过程
1.4平均情形分析
1.5例：快速排序的分析
1.6渐近逼近
1.7分布
1.8概率算法
参考文献
第2章递归关系
2.1基本性质
2.2一阶递归
2.3非线性一阶递归
2.4高阶递归
2.5求解递归的方法
2.6二分分治递和二进制数
2.7一般的分治递归
参考文献
第3章生成函数
3.1常规生成函数
3.2指数生成函数
3.3利用生成函数求解递归
3.4生成函数求解递归
3.5利用生成函数进行变换
3.6关于生成函数的函数方程
3.7利用OGF求解三数中值Quicksort递归
3.8利用生成函数的计数
3.9符号方法
3.10拉格郎日反演
3.11概率生成函数
3.12二元生成函数
3.13特殊函数
参考文献
第4章渐近逼近
4.1有关渐近逼近的记号
4.2渐近展开式
4.3渐近展开式的操作
4.4有限和的渐近逼近
4.5欧拉-麦克劳林求和
4.6二元渐近性
4.7拉普拉斯方法
4.8算法分析中的“正态”例
4.9算法分析中的“泊松”例
4.10生成函数的渐近性
参考文献
第5章树
5.1二叉树
5.2树和森林
5.3树的性质
5.4树的算法
5.5二叉查找树
5.6Catalan树中的平均路径长
5.7二叉查找树中的路径长
5.8随机树的可加参数
5.9高
5.10树性质平均情形结果的小结
5.11树和二叉树的表示
5.12无序树
5.13标号树
5.14其他类型的树
参考文献
第6章排列
6.1提列的基本性质
6.2排列的算法
6.3排列的表示法
6.4计数问题
6.5利用CGF分析排列的性质
6.6逆序与插入排序
6.7左向右最小值与选择排序
6.8圈与原位排列
6.9极值参数
参考文献
第7章串与trie树
7.1串查找
7.2位串的组合性质
7.3规则表达式
7.4有限状态自动机与Knuth-Morris-Pratt算法
7.5上下文无关语法
7.6trie树
7.7trie算法
7.8trie树的组合性质
7.9更大的字母表
参考文献
第8章字与映射
8.1使用分离链接的散列
8.2字的基本性质
8.3生日悖论与赠券收藏家问题
8.4占有约束与极值参数
8.5占有分布
8.6开放定址散列法
8.7映射
8.8整数因子分解与映射
参考文献
索引