计算机算法导论-第9章课件.ppt

1、 1 8/6/2022Introduction to Algorithms9 Medians and Order Statistics 2 8/6/2022Order StatisticsThe ith order statistic in a set of n elements is the ith smallest elementThe minimum is thus the 1st order statistic The maximum is the nth order statisticThe median is the n/2 order statisticIf n is even,

2、there are 2 medians 3 8/6/2022Selection ProblemInput:A set A of n(distinct)numbers and a number i,with 1 i n.Output:The element x A that is larger than exactly i-1 other elements of A.How can we calculate order statistics?What is the running time?4 8/6/20229.1 Minimum and Maximum 5 8/6/2022Minimum a

3、nd MaximumHow many comparisons are needed to find the minimum element in a set?The maximum?MINIMUM(A)1 min A1 2 for i 2 to lengthA 3 do if min Ai 4 then min Ai 5 return min 6 8/6/2022Simultaneous Minimum and MaximumCan we find the minimum and maximum with less than twice the cost?Yes:Walk through el

4、ements by pairsCompare each element in pair to the otherCompare the largest to maximum,smallest to minimumTotal cost:3 comparisons per 2 elements 3 n/2 =O(3n/2)7 8/6/20229.2 Selection in expected linear time 8 8/6/2022The Selection ProblemA more interesting problem is selection:finding the ith small

5、est element of a set We will show:A practical randomized algorithm with O(n)expected running timeA cool algorithm of theoretical interest only with O(n)worst-case running time 9 8/6/2022Randomized SelectionKey idea:use partition()from quicksortBut,only need to examine one subarrayThis savings shows

6、up in running time:O(n)We will again use a slightly different partition q=RandomizedPartition(A,p,r)Aq Aqqpr 10 8/6/2022Randomized SelectionRandomizedSelect(A,p,r,i)if(p=r)then return Ap;q=RandomizedPartition(A,p,r)k=q-p+1;if(i=k)then return Aq;if(i k)then return RandomizedSelect(A,p,q-1,i);else ret

7、urn RandomizedSelect(A,q+1,r,i-k);Aq Aqkqpr 11 8/6/2022Randomized SelectionAnalyzing RandomizedSelect()Worst case:partition always 0:n-1T(n)=T(n-1)+O(n)=?=O(n2)(arithmetic series)No better than sorting!“Best”case:suppose a 9:1 partitionT(n)=T(9n/10)+O(n)=?=O(n)(Master Theorem,case 3)Better than sort

8、ing!What if this had been a 99:1 split?12 8/6/2022Randomized Selection 13 8/6/2022Randomized Selection 14 8/6/2022Calculating expectation 15 8/6/2022Calculating expectation 16 8/6/2022Calculating expectation 17 8/6/2022Calculating expectation 18 8/6/2022Calculating expectation 19 8/6/2022Randomized

9、SelectionLets show that T(n)=O(n)by substitution 12/1021,max1nnknknkTnnknkTnnTWhat happened here?20 8/6/2022What happened here?“Split”the recurrenceWhat happened here?What happened here?What happened here?Randomized SelectionAssume T(n)cn for sufficiently large c:nncncnnnnnncnkkncncknnkTnnTnknknnknn

10、k122121221121222)(2)(1211112/12/The recurrence we started withSubstitute T(n)cn for T(k)Expand arithmetic seriesMultiply it out 21 8/6/2022What happened here?Subtract c/2What happened here?What happened here?What happened here?Randomized SelectionAssume T(n)cn for sufficiently large c:The recurrence

11、 so farMultiply it out Rearrange the arithmeticWhat we set out to prove enough)big is c if(2424241221)(cnnccncnnccncnnccnccnnncncnT 22 8/6/2022Summary of randomized order-statistic selection Works fast:linear expected time.Excellent algorithm in practice.But,the worst case is very bad:(n2).23 8/6/20

12、229.3 Selection in worst-case linear time 24 8/6/2022Worst-Case Linear-Time SelectionWhat follows is a worst-case linear time algorithm,really of theoretical interest onlyBasic idea:Generate a good partitioning elementCall this element x 25 8/6/2022Worst-Case Linear-Time SelectionThe algorithm in wo

13、rds:1.Divide n elements into groups of 52.Find median of each group(How?How long?)3.Use Select()recursively to find median x of the n/5 medians4.Partition the n elements around x.Let k=rank(x)5.if(i=k)then return xif(i k)use Select()recursively to find(i-k)th smallest element in last partition 26 8/

14、6/2022Choosing the pivot 27 8/6/2022Choosing the pivot 28 8/6/2022Choosing the pivot 29 8/6/2022Choosing the pivot 30 8/6/2022Analysis 31 8/6/2022Analysis(Assume all elements are distinct.)32 8/6/2022Analysis(Assume all elements are distinct.)33 8/6/2022Worst-Case Linear-Time SelectionHow many of th

15、e 5-element medians are x?At least 1/2 of the medians=n/5/2=n/10How many elements are x?At least 3 n/10 elementsFor large n,3 n/10 n/4(How large?)So at least n/4 elements xSimilarly:at least n/4 elements x 34 8/6/2022Worst-Case Linear-Time Selection 35 8/6/2022Worst-Case Linear-Time SelectionThus af

16、ter partitioning around x,step 5 will call Select()on at most 3n/4 elementsThe recurrence is therefore:enough big is if20)(2019)(435435435)(ccnncncnncnncncnnnTnTnnTnTnT?n/5 n/5Substitute T(n)=cnCombine fractions Express in desired formWhat we set out to prove 36 8/6/2022Linear-Time Median SelectionG

17、iven a“black box”O(n)median algorithm,what can we do?ith order statistic:Find median xPartition input around xif(i (n+1)/2)recursively find ith element of first halfelse find(i-(n+1)/2)th element in second halfT(n)=T(n/2)+O(n)=O(n)Can you think of an application to sorting?37 8/6/2022Worst-Case Line

18、ar-Time SelectionIntuitively:Work at each level is a constant fraction(19/20)smallerGeometric progression!38 8/6/2022Linear-Time Median SelectionWorst-case O(n lg n)quicksortFind median x and partition around itRecursively quicksort two halvesT(n)=2T(n/2)+O(n)=O(n lg n)39 8/6/2022The EndExercises9.1-1;9.2-4;9.3-8,9