出版者的话译者序 前言 第1章算法分析1.1分析算法1.1.1伪代码1.1.2随机存取机模型1.1.3基本操作数目的计算1.1.4递归算法的分析1.1.5渐近表示法1.1.6渐近表示法的重要性1.2相关数学知识复习1.2.1求和1.2.2对数和幂1.2.3简单的证明技术1.2.4概率基础1.3算法分析案例1.3.1最大子数组问题的第一个解1.3.2一种改进的求最大子数组算法1.3.3线性时间的最大子数组算法1.4平摊分析1.4.1平摊技术1.4.2对一个可扩展数组实现的分析1.5练习本章注记第一部分数据结构第2章基本数据结构2.1栈和队列2.1.1栈2.1.2队列2.2列表2.2.1基于索引的列表2.2.2链表2.3树2.3.1树的定义2.3.2树的遍历2.3.3二叉树2.3.4表示树的数据结构2.4练习本章注记第3章二叉搜索树3.1搜索和更新3.1.1二叉搜索树的定义3.1.2二叉搜索树中的搜索3.1.3二叉搜索树中的插入3.1.4二叉搜索树中的删除3.1.5二叉搜索树的性能3.2范围查询3.3基于索引的搜索3.4随机构造二叉搜索树3.5练习本章注记第4章平衡二叉搜索树4.1秩和旋转4.2AVL树4.3红黑树4.4弱AVL树4.5伸展树4.6练习本章注记第5章优先队列和堆5.1优先队列5.2PQ排序、选择排序和插入排序5.2.1选择排序5.2.2插入排序5.3堆5.3.1基于数组结构的二叉树5.3.2堆中的插入5.3.3堆中的删除5.4堆排序5.5扩展优先队列5.6练习本章注记第6章散列表6.1映射6.1.1映射的定义6.1.2查找表6.2散列函数6.2.1分量求和6.2.2多项式求值函数6.2.3基于表格的散列6.2.4取模6.2.5随机线性和多项式函数6.3碰撞处理与再散列6.3.1拉链法6.3.2开放寻址法6.3.3线性探测6.3.4平方探测6.3.5双重散列6.3.6再散列6.4布谷鸟散列6.5通用散列6.6练习本章注记第7章并查集结构7.1并查集及其应用7.1.1连通分支7.1.2迷宫建筑和渗透理论7.2基于列表的实现7.3基于树的实现7.4练习本章注记第二部分排序和选择第8章归并排序和快速排序8.1归并排序8.1.1分而治之8.1.2归并排序和递推方程8.2快速排序8.2.1随机快速排序8.2.2原地快速排序8.3基于比较的排序的下界8.4练习本章注记第9章快速排序和选择9.1桶排序和基数排序9.1.1桶排序9.1.2基数排序9.2选择9.2.1随机快速选择9.2.2确定性选择9.3加权中位数9.4练习本章注记第三部分基本技术第10章贪心法10.1分份背包问题10.2任务调度10.3文本压缩和哈夫曼编码10.4练习本章注记第11章分治法11.1递推与主定理11.2整数乘法11.3矩阵乘法11.4极大点集问题11.5练习本章注记第12章动态规划12.1矩阵连乘12.2通用技术12.3望远镜调度12.4博弈策略12.4.1硬币行12.4.2概率博弈策略与逆向归纳法12.5最长公共子序列问题12.5.1问题定义12.5.2应用动态规划解LCS问题12.60-1背包问题12.7练习本章注记第13章图及遍历13.1图的术语和表示方法13.1.1图的一些术语13.1.2图的操作13.1.3表示图的数据结构13.2深度优先搜索13.3广度优先搜索13.4有向图13.4.1遍历有向图13.4.2传递闭包13.4.3有向DFS和垃圾回收13.4.4有向无环图13.5双连通分量13.6练习本章注记第四部分图算法第14章最短路径14.1单源最短路径14.2Dijkstra算法14.3BellmanFord 算法14.4有向无环图中的最短路径14.5所有顶点对之间的最短路径14.5.1动态规划最短路径算法14.5.2通过矩阵乘法计算最短路径14.6练习本章注记第15章最小生成树15.1最小生成树的性质15.2Kruskal算法15.3PrimJarník算法15.4Baruvka算法15.5练习本章注记第16章网络流和匹配16.1流与割16.1.1割16.1.2剩余容量和增流路径16.2最大流算法16.2.1FordFulkerson算法16.2.2EdmondsKarp算法16.3最大二分图匹配16.4棒球赛的淘汰16.5最低成本流16.6练习本章注记第五部分计算困难问题第17章NP完全性17.1P和NP17.1.1定义复杂类P和NP17.1.2一些有趣的NP问题17.2NP完全性17.2.1多项式时间归约和NP难度17.2.2CookLevin 定理17.2.3如何证明一个问题是NP完全问题17.3合取范式可满足问题和3可满足问题17.4顶点覆盖、团和集合覆盖17.5子集和与背包问题17.6哈密顿回路和TSP17.7练习本章注记第18章近似算法18.1几何旅行商问题18.1.1MetricTSP的一个2近似算法18.1.2Christofides近似算法18.2覆盖问题的近似18.2.1顶点覆盖的2近似算法18.2.2集合覆盖的对数近似18.3多项式时间近似方法18.4回溯和分支定界18.4.1回溯法18.4.2分支定界法18.5练习本章注记第六部分高级主题第19章随机算法19.1随机排列的生成19.2稳定婚姻和优惠券收集19.2.1优惠券收集问题分析19.2.2稳定婚姻问题19.3最小割19.3.1收缩边19.3.2计算最小割19.3.3更快的算法19.4寻找素数19.5切尔诺夫界19.5.1马尔可夫不等式19.5.2示性随机变量之和19.5.