算法导论中文第三版Chapter 9
一些概念
- 顺序统计量：在n元素集合中，第i个顺序统计量是该集合中第i小的元素。
- 中位数：所属集合的中点元素。如果集合元素数为奇数，那么它的中位数是唯一的；如果集合元素数为偶数，那么它的中位数有两个，较小（或较前）的数称为下中位数，较大（或较后）的数称为上中位数。
- 最大值：第一个顺序统计量。
- 最小值：最后一个顺序统计量。
顺序统计量选择问题
- 输入：一个包含n个（互异）数的集合A和一个整数i，1≤i≤n。
- 输出：元素x∈A，且A中恰好有i-1个元素小于x。
的
在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中第i小的元素。例如，在一个元素集合中，最小值是第1个顺序统计量(i=1)，最大值是第n个顺序统计量(i=n)。用非形式化的描述来说，一个中位数(median)是它所属集合的“中点元素”。当n为奇数时，中位数是唯一的，位于i=(n+1)/2处。当n为偶数时，存在两个中位数，分别位于i=n/2和i=n/2+1处。因此，如果不考虑n的奇偶性，中位数总是出现在i=floor((n+1)/2)处（下中位数）和i=ceil((n+2)/2)处（上中位数）。为了简便起见，本书中所用的“中位数”都是指下中位数。本章将讨论从一个由n个互异的元素构成的集合中选择第i个顺序统计量的问题。为了方便起见，假设集合中的元素都是互异的，但实际上我们所做的都可以推广到集合中包含重复元素的情形。我们将这一问题形式化定义为如下的选择问题：输入：一个包含n个（互异的）数的集合A和一个整数i, 1<=i<=n。输出：元素x属于A，且A中恰好有i-1个其他元素小于它。我们可以在O(nlgn)时间内解决这个问题，因为我们可以用堆排序或归并排序对输入数据进行排序，然后在输出数组中根据下标找出第i个元素即可。本章将介绍一些更快的算法。在9.1节中，我们将讨论从一个集合中选择最小元素和最大元素的问题。对于一般化选择问题的更有意思的讨论将在接下来的两节中进行。9.2节将分析一个实用的随机算法，它在元素互异的假设条件下可以达到O(n)的期望运行时间。9.3节将给出一个更具有理论意义的算法，它在最坏情况下的运行时间为O(n)。
9.1 最小值和最大值在一个有n个元素的集合中，需要做多少次比较才能确定其最小元素呢？我们可以很容易地给出n-1次比较这个上界：依次遍历集合中的每个元素，并记录下当前最小元素。在下面的程序中，我们假设该集合元素存放在数组A中，且A.length=n：
当然，最大值也可以通过n-1次比较找出来。这是我们能得到的最好结果吗？是的，对于确定最小值问题，我们可以得到其下界就是n-1次比较。对于任意一个确定最小值的算法，可以把它看成是各元素之间进行的一场锦标赛。每次比较都是锦标赛中的一场比赛，两个元素中较小的获胜。需要注意的是，除了最终获胜者以外，每个元素都至少要输掉一场比赛。因此，我们得到结论：为了确定最小值，必须要做n-1次比较。因此，从所执行的比较次数来看，算法MINIMUM是最优的。同时找到最小值和最大值在某些应用中，我们必须要找出一个包含n个元素的集合中的最小值和最大值。例如，一个图形程序可能需要转换一组(x, y)数组，使之能适合一个矩形显示器或其他图形输出装置。为了做到这一点，程序必须首先确定每个坐标中的最小值和最大值。就这一点来说，用渐近最优的THETA(n)次比较，在n个元素中同时找到最小值和最大值的方法是显然的：只要分别独立地找出最小值和最大值，这各需要n-1次比较，共需2n-2次比较。事实上，我们只需要最多3floor(n/2)次比较就可以同时找到最小值和最大值。具体的方法是记录已知的最小值和最大值。但我们并不是将每一个输入元素与当前的最小值和最大值进行比较——这样做的代价是每个元素需要2次比较，而是对输入元素成对地进行处理。首先，我们将一对元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，对每两个元素共需3次比较。如何设定已知的最小值和最大值的初始值依赖于n是奇数还是偶数。如果n是奇数，我们就将最小值和最大值的初值都设为第一个元素的值，然后成对地处理余下的元素。如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与n是奇数的情形一样，成对地处理余下的元素。下面来分析一下总的比较次数。如果n是奇数，那么总共进行3floor(n/2)次比较。如果n是偶数，则是先进行一次初始比较，然后进行3(n-2)/2次比较，共3n/2-2次比较。因此，不管是哪一种情况，总的比较次数至多是3floor(n/2)。练习9.1-1 证明：在最坏情况下，找到n个元素中第二小的元素需要n+ceil(lgn)-2次比较。（提示：可以同时找最小元素。）http://clrs.skanev.com/09/01/01.html* 9.1-2 证明：在最坏情况下，同时找到n个元素中最大值和最小值的比较次数的下界是ceil(3n/2)-2。（提示：考虑有多少个数有成为最大值或最小值的潜在可能，然后分析一下每一次比较会如何影响这些计数。）http://clrs.skanev.com/09/01/02.html
作者：Beryllium链接：http://www.jianshu.com/p/148f4417b6bb來源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
一般选择问题看起来要比找最小值这样的简单问题更难。但令人惊奇的是，这两个问题的渐近运行时间却是相同的：THETA(n)。本节将介绍一种解决选择问题的分治算法。RANDOMIZED-SELECT算法是以第7章的快速排序算法为模型的。与快速排序一样，我们仍然将输入数组进行递归划分。但与快速排序不同的是，快速排序会递归处理划分的两边，而RANDOMIZED-SELECT只处理划分的一边。这一差异会在性能分析中体现出来：快速排序的期望运行时间是THETA(nlgn)，而RANDOMIZED-SELECT的期望运行时间为THETA(n)。这里，假设输入数据都是互异的。RANDOMIZED-SELECT利用了7.3节介绍的RANDOMIZED-PARTITION过程。与RANDOMIZED-QUICKSORT一样，因为它的部分行为是由随机数生成器的输出决定的，所以RANDOMIZED-SELECT也是一个随机算法。以下是RANDOMIZED-SELECT的伪代码，它返回数组A[p..r]中第i小的元素。
RANDOMIZED-SELECT的运行过程如下：第1行检查递归的基本情况，即A[p..r]中只包括一个元素。在这种情况下，i必然等于1，在第2行，我们只需将A[p]返回作为第i小的元素即可。其他情况，就会调用第3行的RANDOMIZED-PARTITION，将数组A[p..r]划分为两个（可能为空的）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于或等于A[q]，而A[q]小于A[q+1..r]中的每个元素。与快速排序中一样，我们称A[q]为主元(pivot)。RANDOMIZED-SELECT的第4行计算子数组A[p..q]内的元素个数k，即处于划分的低区的元素的个数加1，这个1指主元。然后，第5行检查A[q]是否是第i小的元素。如果是，第6行就返回A[q]。否则，算法就要确定第i小的元素落在两个子数组A[p..q-1]和A[q+1..r]的哪一个之中。如果i<k，则要找的元素落在划分的低区。第8行就在低区的子数组中进一步递归查找。如果i>k，则要找的元素落在划分的高区中。因为我们已经知道了有k个值小于A[p..r]中第i小的元素，即A[p..q]内的元素，所以，我们所要找的元素必然是A[q+1..r]中的第i-k小的元素。它在第9行中被递归地查找。上述程序看起来允许递归调用含有0个元素的子数组，但练习9.2-1要求证明这种情况不可能发生。RANDOMIZED-SELECT的最坏情况运行时间为THETA(n^2)，即使是找最小元素也是如此，因为在每次划分时可能极不走运地总是按余下的元素中最大的来进行划分，而划分操作需要THETA(n)的时间。我们也将看到该算法有线性的期望运行时间，又因为它是随机化的，所以不存在一个特定的会导致其最坏情况发生的数据。为了分析RANDOMIZED-SELECT的期望运行时间，我们设该算法在一个含有n个元素的输入数组A[p..r]上的运行时间是一个随机变量，记为T(n)。下面我们可以得到E[T(n)]的一个上界：程序RANDOMIZED-SELECT能等概率地返回任何元素作为主元。因此，对每一个k(1<=k<=n)，子数组A[p..q]有k个元素（全部小于或等于主元）的概率是1/n。对所有k=1, 2, ..., n，定义指示器随机变量Xk为：
然后，假设元素是互异的，我们有：
（9.1）
当调用RANDOMIZED-SELECT并选择A[q]作为主元时，事先并不知道是否会立即得到正确答案而结束，或者在子数组A[p..q-1]上递归，或者在子数组A[q+1..r]上递归。这个决定依赖于第i小的元素相对于A[q]落在哪个位置。假设T(n)是单调递增的，通过评估最大可能的输入数据递归调用所需时间，我们可以给出递归调用所需时间的上界。也就是说，为了得到上界，我们假定第i个元素总是在划分中包含较大元素的一边。对一个给定的RANDOMIZED-SELECT，指示器随机变量Xk恰好在给定的k值取1，对其他值都为0。当Xk=1时，我们可能要递归处理的两个子数组的大小分别为k-1和n-k。因此可以得到递归式：
两边取期望值，得到
公式(C.24)的应用依赖于Xk和T(max(k-1, n-k))是独立的随机变量。练习9.2-2要求证明这个命题。下面来考虑一下表达式max(k-1, n-k)。我们有
如果n是偶数，则从T(ceil(n/2))到T(n-1)的每一项在总和中恰好出现两次。如果n是奇数，除了T(floor(n/2))出现一次意外，其他这些项也都会出现两次。因此，我们有
我们将用替代法来得到E[T(n)]=O(n)。假设对满足这个递归式初始条件的某个常数c，有E[T(n)]<=cn。假设对小于某个常数的n，有T(n)=O(1)（稍后将用到这个常数）。同时，还要选择一个常数a，使得对所有的n>0，上式中O(n)项所描述的函数（用来表示算法运行时间中的非递归部分）有上界an。利用这个归纳假设，可以得到：
为了完成证明，还需要证明：对足够大的n，最后一个表达式至多是cn，等价地，cn/4-c/2-an>=0。如果在上式两边加上c/2，并且提取因子n，就可以得到n(c/4-a)>=c/2。只要我们选择的常数c能够满足c/4-a>0，即c>4a，就可以将两边同除以c/4-a，得到
因此，如果假设对所有n<2c/(c-4a)，都有T(n)=O(1)，那么就有E[T(n)]=O(n)。我们可以得出这样的结论：假设所有元素是互异的，在期望线性时间内，我们可以找到任一顺序统计量，特别是中位数。练习9.2-1 证明：在RANDOMIZED-SELECT中，对长度为0的数组，不会进行递归调用。9.2-2 请讨论：指示器随机变量Xk和T(max(k-1, n-k))是独立的。9.2-3 给出RANDOMIZED-SELECT的一个基于循环的版本。9.2-4 假设用RANDOMIZED-SELECT去选择数组A=<3, 2, 9, 0, 7, 5, 4, 8, 6, 1>的最小元素，给出能够导致RANDOMIZED-SELECT最坏情况发生的一个划分序列。
作者：Beryllium链接：http://www.jianshu.com/p/3ff11606328a來源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
