第一部分 基础知识
第二部分 排序和顺序统计量
第三部分 数据结构
第四部分 高级设计和分析技术
第五部分 高级数据结构
第六部分 图算法
第七部分 算法问题选编
---------------------------------------------------------------------------------------------------------------------------------------------------------------
第1章 算法在计算中的作用
思考题
1-1 (运行时间的比较) 假设求解问题的算法需要f(n)毫秒,对下表中的每个函数f(n)和时间t,确定可以在时间t内求解的问题的最大规模n
| 1秒钟 | 1分钟 | 1小时 | 1天 | 1月 | 1年 | 1世纪 | |
| lgn | |||||||
| sqrt(n) | |||||||
| n | |||||||
| nlgn | |||||||
| n^2 | |||||||
| n^3 | |||||||
| 2^n | |||||||
| n! |
第2章 算法基础
练习
2.2-1 用 记号表示函数n^3/1000-100n^2-100n+3
Θ(n^3)
2.2-2 考虑排序存储在数组A中的n个数:首先找出A中的最小元素并将其与A[1]中的元素进行交换.接着,找出A中的次最小元素并将其与A[2]中的元素进行交换.对A中前n-1个元素按该方式继续.该算法称为选择算法,写出其伪代码.该算法维持的循环不变式是什么?为什么它只需要对前n-1个元素,而不是对所有n个元素运行?用Θ记号给出选择排序的最好情况与最坏情况运行时间.
2.2-3 再次考虑线性查找问题(参见练习2.1-3).假定要查找的元素等可能地为数组中的任意元素,平均需要检查输入序列的多少元素?最坏情况又如何呢?用Θ记号给出线性查找的平均情况和最坏情况运行时间.证明你的答案.
2.2-4 应该如何修改任何一个算法,才能使之具有良好的最好情况运行时间?
第3章 函数的增长
第4章 分治策略
第5章 概率分析和随机算法
第6章 堆排序
第7章 快速排序
第8章 线性时间排序
第9章 中位数和顺序统计量
第10章 基本数据结构
第11章 散列表
第12章 二叉搜索树
第13章 红黑树
第14章 数据结构的扩张
第15章 动态规划
第16章 贪心算法
第17章 摊还分析
第18章 B树
第19章 斐波那契堆
第20章 van Emde Boas 树
第21章 用于不相交集合的数据结构
第22章 基本的图算法
第23章 最小生成树
第24章 单源最短路径
第25章 所有结点对的最短路径问题
第26章 最大流
第27章 多线程算法
第28章 矩阵运算
第29章 线性规划
第30章 多项式与快速傅里叶变换
第31章 数论算法
第32章 字符串匹配
第33章 计算几何学
第34章 NP完全性
第35章 近似算法
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------