计算机算法基础 第2版 课件 第5章 中位数和任一顺序数的选择.pptx

1第5章中位数和任一顺序数的选择问题定义 2最大和最小数的选择算法 4同时找出最大数和最小数的算法 7线性时间找任一顺序数的算法 10保证最坏情况复杂度是O(n)的算法 11平均情况复杂度为O(n)的算法 17找出k个最大顺序数的算法 18

2?1.问题定义

3?

4找最大顺序数算法如下：Maximum(A[1..n],max)max←A[1]fori←2ton ifmaxA[i] thenmax←A[i] endifendforreturnmaxEnd找最小数类似。这个算法需要(n-1)次比较。问题：能否用少於(n-1)次比较来找到最大数呢？2.最大和最小数的选择算法

5定理5.1 任何基於比较的算法在n个不等的数字中找出最大顺序数（或最小顺序数）需要至少n-1次比较。证明：因对称，我们只证最大数的情况。 我们把每次比较中较大的数称为胜者，而较小的数为败者。那么，数x是最大顺序数的充要条件是：它必须和某些其他的数比较过，并且每次都是胜者。其他的n-1个数都必须和某些数比较过并且至少有一次是败者。如果每次比较后都在败者上打一个印记，那么除了最大数，每个数都会被打上至少一次印记，总的印记数至少是n-1。因为每次比较只打一个印记，所以比较次数至少是n-1。?类似地可证明，找最小顺序数也需要至少n-1次比较。注意，这个下界是所有情况的下界，包括最好情况。

6定理5.2 如果事先不知道输入的n个数字中，任何两个数字的大小关系，包括大于、小于、和相等，那么任何基于比较的算法在这n个数字中找出最大(或最小)数，至少需要n-1次比较。证明： 因对称，只证最大数的情况。构造图G，初始只有n个顶点，代表这n个数。如果算法将数a和数b作一次比较，则在代表a和b的两顶点之间画一条边。算法结束时，边的个数就是比较次数。可证明G是连通图。否则，必有连通子图C，它和算法报告的最大数对应的点无通路。我们可把C中每个数都加上同一个很大的数M，使最大数不再是原来的数，而是C里的一个数。因为C中点之间相对大小不会变，如果让算法对更改后的n个数再找一次最大数的话，算法不会察觉更改，而仍会输出相同的最大数。这就错了。因此，图G必须是个连通图。因为有n个顶点的连通图必定含有至少n-1条边，所以该算法至少用了n-1次比较，定理得证。?

7如果分别找出最大和最小数，则需要2n-3次比较。同时把它们找出的步骤如下：(1) 顺序把每两个数字配为一组，即 A[1]和A[2]为第1组，A[3]和A[4]为第2组，…， 如果n是奇数，则最后一组只含一个数A[n]。(2) 比较A[1]和A[2]，大者放入变量max，而小者放入变量min(3) 从第2组开始，每组做3次比较：比较组内两个数决出谁大谁小。 (如只含A[n]，不需比较，A[n]既是大者又是小者。)大者和当前max中的数比较以更新max小者和当前min中的数比较以更新min。(伪码见下页)3.同时找出最大数和最小数的算法

8Maximum-minimum(A[1..n],max,min)ifn=1 thenmax←min←A[1]，exit，endifmin←min{A[1],A[2]}，max←max{A[1],A[2]} //第1组处理完ifn2 then fork←2to?n/2? ifA[2k-1]A[2k] then min←min{A[2k-1],min} max←max{A[2k],max} else min←min{A[2k],min} max←max{A[2k-1],max} endif endfor if2kn //n是奇数的情况 then min←min{A[n],min} max←max{A[n],max} endifendifEnd

9?

10讨论如何从n个数中找出第i顺序数的问题(1?i?n)。介绍两个算法：(1) 保证最坏情况复杂度是O(n)的算法。(2) 平均情况复杂度是O(n)的算法。第一个算法的理论价值大于实际价值，因为它不仅实现起来很复杂，而且时间O(n)中含有很大常数。4.线性时间找任一顺序数的算法

11保证最坏情况复杂度是O(n)的算法Select(setA,n,i) //1?i?n如果n?5，则排序后直接得到第i顺序数，分治法的底。每5个数为分