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

《计算机算法导论第9章ppt课件》由会员分享，可在线阅读，更多相关《计算机算法导论第9章ppt课件（39页珍藏版）》请在装配图网上搜索。

1、Introduction to Algorithms9 Medians and Order StatisticsOrder 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,there are 2 mediansSel

2、ection 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?9.1 Minimum and MaximumMinimum and MaximumHow many comparisons are needed to find the

3、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 Simultaneous Minimum and MaximumCan we find the minimum and maximum with less than twice the cost?Yes:Walk through elements by pairsCompare each element in pair to the otherCompare

4、the largest to maximum,smallest to minimumTotal cost:3 comparisons per 2 elements 3 n/2=O(3n/2)9.2 Selection in expected linear timeThe Selection ProblemA more interesting problem is selection:finding the ith smallest element of a set We will show:A practical randomized algorithm with O(n)expected r

5、unning timeA cool algorithm of theoretical interest only with O(n)worst-case running timeRandomized SelectionKey idea:use partition()from quicksortBut,only need to examine one subarrayThis savings shows up in running time:O(n)We will again use a slightly different partition q=RandomizedPartition(A,p

6、,r)Aq AqqprRandomized 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 return RandomizedSelect(A,q+1,r,i-k);Aq AqkqprRandomized SelectionAnalyzing RandomizedSelect()Worst case:partiti

7、on 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 sorting!What if this had been a 99:1 split?Randomized SelectionRandomized SelectionCalculating expectationCalculating expecta

8、tionCalculating expectationCalculating expectationCalculating expectationRandomized SelectionLets show that T(n)=O(n)by substitution 12/1021,max1nnknknkTnnknkTnnTWhat happened here?What happened here?“Split the recurrenceWhat happened here?What happened here?What happened here?Randomized SelectionAs

9、sume T(n)cn for sufficiently large c:nncncnnnnnncnkkncncknnkTnnTnknknnknnk122121221121222)(2)(1211112/12/The recurrence we started withSubstitute T(n)cn for T(k)Expand arithmetic seriesMultiply it outWhat happened here?Subtract c/2What happened here?What happened here?What happened here?Randomized S

10、electionAssume T(n)cn for sufficiently large c:The recurrence so farMultiply it out Rearrange the arithmeticWhat we set out to prove enough)big is c if(2424241221)(cnnccncnnccncnnccnccnnncncnTSummary of randomized order-statistic selection Works fast:linear expected time.Excellent algorithm in pract

11、ice.But,the worst case is very bad:(n2).9.3 Selection in worst-case linear timeWorst-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 xWorst-Case Linear-Time SelectionThe a

12、lgorithm in words: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 p

13、artitionChoosing the pivotChoosing the pivotChoosing the pivotChoosing the pivotAnalysisAnalysis(Assume all elements are distinct.)Analysis(Assume all elements are distinct.)Worst-Case Linear-Time SelectionHow many of the 5-element medians are x?At least 1/2 of the medians=n/5/2=n/10How many element

14、s 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 xWorst-Case Linear-Time SelectionWorst-Case Linear-Time SelectionThus after partitioning around x,step 5 will call Select()on at most 3n/4 elementsThe recurrence is therefore:e

15、nough big is if20)(2019)(435435435)(ccnncncnncnncncnnnTnTnnTnTnT?n/5 n/5Substitute T(n)=cnCombine fractions Express in desired formWhat we set out to proveLinear-Time Median SelectionGiven a“black box O(n)median algorithm,what can we do?ith order statistic:Find median xPartition input around xif(i (

16、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?Worst-Case Linear-Time SelectionIntuitively:Work at each level is a constant fraction(19/20)smallerGeometric progression!Linear-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)The EndExercises9.1-1;9.2-4;9.3-8,9