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

1、Introduction to Algorithms9 Medians and Order Statistics 1 7/25/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, there are

2、 2 medians 2 7/25/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? 3 7/25/20229.1 Minimum and Maximum 4 7/25/2022Minimu

3、m and 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 5 7/25/2022Simultaneous Minimum and MaximumCan we find the minimum and maximum with less than twice the cost?Yes:Walk thro

4、ugh elements 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) 6 7/25/20229.2 Selection in expected linear time 7 7/25/2022The Selection ProblemA more interesting problem is selection: finding

5、the ith smallest 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 8 7/25/2022Randomized SelectionKey idea: use partition() from quicksortBut, only need to examine one subarray

6、This savings shows up in running time: O(n)We will again use a slightly different partition q = RandomizedPartition(A, p, r) Aq Aqqpr 9 7/25/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 (

7、i k) then return RandomizedSelect(A, p, q-1, i); else return RandomizedSelect(A, q+1, r, i-k); Aq Aqkqpr 10 7/25/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

8、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? 11 7/25/2022Randomized Selection 12 7/25/2022Randomized Selection 13 7/25/2022Calculating expectation 14 7/25/2022Calculating expectation 15 7/25/2022Calculating expectation 16 7

9、/25/2022Calculating expectation 17 7/25/2022Calculating expectation 18 7/25/2022Randomized SelectionLets show that T(n) = O(n) by substitutionWhat happened here? 19 7/25/2022What happened here?“Split” the recurrenceWhat happened here?What happened here?What happened here?Randomized SelectionAssume T

10、(n) cn for sufficiently large c:The recurrence we started withSubstitute T(n) cn for T(k) Expand arithmetic seriesMultiply it out 20 7/25/2022What happened here?Subtract c/2What happened here?What happened here?What happened here?Randomized SelectionAssume T(n) cn for sufficiently large c:The recurr

11、ence so farMultiply it out Rearrange the arithmeticWhat we set out to prove 21 7/25/2022Summary of randomized order-statistic selection Works fast: linear expected time. Excellent algorithm in practice. But, the worst case is very bad: (n2). 22 7/25/20229.3 Selection in worst-case linear time 23 7/2

12、5/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 24 7/25/2022Worst-Case Linear-Time SelectionThe algorithm in words:1.Divide n elements into groups of 52.Fi

13、nd 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 25 7/25/2022Choosing the pivot 26 7

14、/25/2022Choosing the pivot 27 7/25/2022Choosing the pivot 28 7/25/2022Choosing the pivot 29 7/25/2022Analysis 30 7/25/2022Analysis(Assume all elements are distinct.) 31 7/25/2022Analysis(Assume all elements are distinct.) 32 7/25/2022Worst-Case Linear-Time SelectionHow many of the 5-element medians

15、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 33 7/25/2022Worst-Case Linear-Time Selection 34 7/25/2022Worst-Case Linear-Time SelectionThus after parti

16、tioning around x, step 5 will call Select() on at most 3n/4 elementsThe recurrence is therefore: ? n/5 n/5Substitute T(n) = cnCombine fractions Express in desired formWhat we set out to prove 35 7/25/2022Linear-Time Median SelectionGiven a “black box” O(n) median algorithm, what can we do?ith order

17、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? 36 7/25/2022Worst-Case Linear-Time SelectionIntuitively:Work at each level is a constant fraction (1