讲-中位数与顺序统计.pptxVIP

算法分析与设计

中位数与顺序统计(Ch9)

SimpleReview计数排序如果A中有17个元素不大于x?将最后一个x放位置17，倒数第二个x放位置16，…若k=O(n),则计数排序的计算时间为Θ(n)。基数排序利用稳定的排序算法首先按照最低位排序。Θ(dT(n)),如果使用计数排序且d为常数，则计算时间为Θ(n)桶排序将区间[0,1)分为n个大小相等的子区间，或桶，然后将n个输入数据分布到这些桶中。均匀分布时，计算时间为Θ(n)。

算法分析与设计中位数与顺序统计内容:顺序统计线性期望时间的选取算法最坏情况线性时间的选取算法

主要内容中位数与顺序统计两个O(n)的算法:随机算法:与快排类似确定化算法:精心设计的算法(tricky)两个算法均是分治策略的应用

顺序统计顺序统计:n个元素构成的集合中，其第i个顺序统计定义为集合中的第i小元素。中位数集合中的中值元素。后续使用“中位数”指下中位数。选取n个元素构成的集合中的第i小元素(即位置为i元素).最小值:i=1：最大值:i=n中位数:效率?O(n)：求最小值或最大值。O(nlgn)：基于排序选取任意i。O(nlgi)：基于堆实现。下面我们将学习如何在线性时间内完成。

求最大最小值在一个有n个元素的集合中，要做多少次比较才能确定其最小元素呢？可以很容易地给出n-1这个上界：依次查看集合中的每个元素，并记录比较过程中的最小元素。我们可以独立地找出最大值和最小值，各用n-1次比较。事实上，至多3(n/2)次比较久足以同时找到最小值和最大值。做法是记录比较过程遇到的最小值和最大值。我们不是将每一个输入元素与当前的最大值和最小值进行比较。而是成对地处理元素。先将一对输入元素互相比较，然后把较大的与当前最大值进行比较，较小的与当前最小值进行比较，因此每对元素需要比较3次。

练习证明：在最坏情况下，利用n+lgn-2次比较，即可以找到n个元素中的第2小的元素。参考答案：（从网上找的答案）将n个元素进行两两比较，将较大的淘汰，较小的留下。这样通过n/2次比较就剩下n/2个元素。再进行第二轮；如此往复直到得出最小的元素。这个过程可以用一棵二叉树来描述。那么第二小的元素只有在于最小元素的比较才会被淘汰。最小的元素进行过的元素有lgn-1个。于是在进行lgn-2次比较就可以得出第二小的元素。PS：这个解法的问题在于，如何记住与最小元素比较过的元素集合，难道要整棵树建出来。这样的话这个算法没有什么实际意义。

以期望线性时间做选择一般的选择问题比找最小值的简单问题更难，两种问题的渐进运行时间却是相同的都是Θ(n)。本节介绍一种解决选择问题的分治算法，即RANDOMIZED-SELECT算法，以快速排序算法为模型，如同在排序中一样，对输入的数组进行递归划分，但和快速排序不同的是，快速排序会递归处理划分的两边，而RANDOMIZED-SELECT只处理划分的一边。RANDOMIZED-SELECT的期望时间为Θ(n)。

查找第i元素的随机算法应用分治策略基本思想:PARTITION若ik,在左部递归求解若ik.在右部递归求解否则，输出x

随机选取算法RANDOMIZDSELECTRANDOMIZED-SELECT(A,p,r,i)1ifp=r2thenreturnA[p]3q←RANDOMIZED-PARTITION(A,p,r)//asusedinquicksort4k←q–p+1//k=rank(A[q])5ifi=k//thepivotvalueistheanswer6thenreturnA[q]7ifik8thenreturnRANDOMIZED-SELECT(A,p,q–1,i)9elsereturnRANDOMIZED-SELECT(A,q+1,r,i–k)

随机选取算法——示例选取第i=7小元素:划分:递归选取第7-4=3小元素RANDOMIZED-PARTITION就是快速排序算法中的partition过程。RANDOMIZED-SELECT的最坏运行时间是n2。期望运行时间为n。

分析最坏情况下的计算时间?回顾：一个比较好的划分将数组分9:1的两部分。幸运:T(n)=T(9n/10)+Θ(n)=Θ(n)倒霉:T(n