算法导论(clrs)笔记

《算法导论(clrs)笔记》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法导论（CLRS）笔记NoteonCLRS(Outline&Draft,2011)1JianXiao第2章Gettingstarted1.Mergesort相关的扩展问题1）链表实现V.S.数组实现。Divide阶段，如何快速找到链表的中点？另外，如何减少Divide/Combine的时间（相比数组实现）？2）In-placemerge的方法。3）归并树：把Mergesort的中间过程都记录下来，所形成的树。（其实就是一棵线段树,每个节点存放该节点的区间内有序化后的数）4）逆序数的计算。2.两数和问题。数的集合S，一个数x，判断S中是否存

2、在两个数，二者的和为x。这个问题扩展以后是一个subsetproblem，为NPC问题。第3章GrowthofFunctions1.全部5个渐进符号的确切含义第4章Recurrences1.Substitution方法，Recursiontree方法计算复杂度2.MasterTheorem及其不能被三种case覆盖的其他情况MasterTheorem的证明3.Chiptestingproblem4.Mongearrays，凸四边形不等式，最优二叉查找树DP算法的优化第5章ProbabilisticAnalysisandRandomizedA

3、lgorithms1.用Biased-Random产生Uniform-Random分布。2.In-place、O(n)的uniformrandompermutationIn-place、O(n)的各个position等概的排列1iamxiaojian@gmail.com3.Couponcollector’sproblem4.On-linehiringproblem第6章Heapsort1.两种建堆的方法：逐个插入的O(nlogn)，以及自底向上调整的O(n)算法2.Heapsort可能存在效率的地方：每次删除堆顶，都是把某树叶放置于堆顶，然

4、后调整；但是，树叶一般比较大，放于堆顶后，几乎总是要进行多次的比较才能恢复堆的结构。3.优先队列：堆,min-maxheap,可合并堆（左偏树，二项树）,stack(栈模拟队列，同时具有高效取最大最小值功能)4.杨氏表1）由数1~n组成的杨氏表的个数2）杨氏表插入：Bumping算法3）杨氏表查找：对角查找，O(m+n)4）杨氏表删除5）杨氏表的排序：一个m*n的表填满数，排序时间应该低于直接快速排序的O(mnlogmn)6）杨氏表的中位数和第k小数第7章QuickSort1.Partition的两个版本：HoarePartition和书中

5、正文的版本2.QuickSort的stackdepth，tailrecursion和最坏O(logn)递归深度的快排方法第8章SortinginLinearTime1.CountingSort以及其稳定性2.RadixSort，其正确性及对IntermediateSort的稳定性的依赖3.BucketSort：N个有序的Bucket，每个点落入每个Bucket的概率是均匀分布。对于从某个分布P(x)中sample而来的点，用类似的方法进行期望线性时间排序。4.AverageSorting问题第9章MediansandOrderStatist

6、ics1.优化的同时选最小值和最大值算法优化的选第二小值算法2.基于QuickSort的Partition方法的期望线性时间选择3.Median-of-Medians最坏线性时间选择算法因此QuickSort可以做到最坏O(nlogn)。4.WeightedMedian的最坏线性时间算法，以及经典应用第10章ElementaryDataStructures1.两个栈模拟一个队列，两个队列模拟一个栈2.left-child,right-sibling表示法3.树的各种非递归遍历第11章Hashfunctions1.Universalhashi

7、ngLocalsensitivehashing共同点是具有一个hash函数集2.Perfecthashing的方法与分析第12章BinarySearchTree1.BST的基本操作：找predecessor和successor；删除节点2.随机BST高度的分析证明3．Binarytree的个数，generatingfunction求解递推公式的通项第13章Red-BlackTree1.红黑树的定义，以及从定义推导出其高度的界2.旋转变换的本质：PreservetheBSTproperty。实现基本旋转变换：左旋和右旋。旋转的实质是保持BST

8、性质的变换；而BST性质是旋转变换的不变量（invariant）。3.红黑树的插入与删除4.保留下树的每个历史形态的结构：Persistentdynamicset。5.Treap