Minimum and MaximumQuick SelectionAnalysisDeterministic AlgorithmExampleRunning TimeCS6363: Design and Analysis of Computer Algorithms Prof. Sergey BeregMedians and Order Statistics1 Minimum and MaximumMINIMUM(A)1 min = A[1]2 for i = 2 to length(A)3 if min > A[i] then4 min = A[i]5 return minThe number of comparisons (line 3) is n − 1.Simultaneous min and max. 2n − 3 comparisons. 3bn/2c?The second smallest element. How many comparisons are needed?2 Quick SelectionThe ith order statistics of a set of n elements is the ith smallest element. A median is defined fori = (n + 1)/2 if n is odd and i = n/2 − 1 (lower median) or i = n/2 + 1 (upper median) if n is even.The selection problem: Given a set A of n (distinct) numbers and a number i with 1 ≤ i ≤ n, find theelement x ∈ A that is larger than exactly i − 1 elements of A.Can be solved by sorting in O(n lg n) time. We show(1) practical algorithm with O(n) expected running time, and(2) theoretical algorithm with O(n) running time in the worst case.RANDOMIZED-SELECT(A, p, r, i)1 if p = r then2 return A[p]3 q =RANDOMIZED-PARTITION(A, p, r)4 k ← q − p + 15 if i = k then // the pivot value is the answer6 return A[q]7 else8 if i < k then9 return RANDOMIZED-SELECT(A, p, q − 1, i)10 else return RANDOMIZED-SELECT(A, q + 1, r, i − k)RANDOMIZED-PARTITION(A, p, r) // Chapter 7, page 154.1 i =RANDOM(p, r)2 exchange A[r] ↔ A[i]3 return PARTITION(A, p, r)1PARTITION(A, p, r) // Chapter 7, page 146.1 x = A[r]2 i = p − 13 for j = p to r − 14 if A[j] ≤ x then5 i = i + 16 exchange A[i] ↔ A[j]7 exchange A[i + 1] ↔ A[r]8 return i + 13 AnalysisLet Xkbe a random variable that is 1 if A[p..q ] contains exactly k elements and Xk= 0 otherwise. Expectedvalue of XkisE[Xk] =1n.If Xk= 1 then RANDOMIZED-SELECT recurses either on A[p..q − 1] or A[q + 1..r]. Let T (n) be therunning time. ThenT (n) ≤ O(n) +nXk=1Xk· T (max(k − 1, n − k))E[T (n)] ≤ E[O(n) +nXk=1Xk· T (max(k − 1, n − k))]= O(n) +nXk=1E[Xk· T (max(k − 1, n − k))] (by linearity of expectation)= O(n) +nXk=1E[Xk] · E[T (max(k − 1, n − k))]= O(n) +nXk=11n· E[T (max(k − 1, n − k))]≤ O(n) +2ndn/2eXk=1E[T (n − k)].Suppose that E[T (n)] ≤ an +2ndn/2eXk=1E[T (n − k)]2We prove E[T (n)] ≤ cn by induction. Step of induction:E[T (n)] ≤ an +2ndn/2eXk=1E[T (n − k)] ≤ an +2ndn/2eXk=1c(n − k)= an + 2cdn/2e −2cndn/2eXk=1k≤ an + 2c(n/2 + 1) −2cn·dn/2e(dn/2e + 1)2≤ an + cn + 2c −2cn·n2(n2+ 1)2= an + cn + 2c −c2n2+ 1= cn −n(c4− a) −5c2≤ cn if n(c4− a) ≥5c2.It holds if c/4 − a ≥ c/8 (or c ≥ 8a) and n ≥ 20.4 Deterministic AlgorithmSELECTION(A, n)1. Divide n elements into dn/5e groups of at most 5 elements each.2. Find median in each group by sorting it.3. Find median-of-medians x recursively (call SELECTION for an array of medians).4. Partition the input array A using pivot x. Let x be kth element of A.5. If i = k then return x. Otherwise recursively find ith element on the low side if i < k, or(i − k)th element on the high side if i > k.5 ExampleGiven an array A with 53 numbersA = {33, 22, 30, 14, 45, 10, 44, 23, 9, 39, 38, 52, 6, 5, 50, 37, 11, 26, 3, 15,2, 53, 40, 54, 25, 55, 12, 19, 31, 16, 18, 13, 1, 48, 41, 24, 43, 46, 47, 17, 34, 20,31, 32, 33, 35, 4, 49, 51, 7, 21, 27, 8}Compute 10th smallest number.Step 1. Divide n elements into dn/5e groups.33 10 38 37 2 55 18 24 34 35 2122 44 52 11 53 12 13 43 20 4 2730 23 6 26 40 19 1 46 31 49 814 9 5 3 54 31 48 47 32 5145 39 50 15 25 16 41 17 33 732. Find the median in each group by sorting it.14 9 5 3 2 12 1 17 20 422 10 6 11 25 16 13 24 31 7 830 23 38 15 40 19 18 43 32 35 2133 39 50 26 53 31 41 46 33 49 2745 44 52 37 54 53 48 47 34 513. Find median-of-medians recursively, i.e. find 6th smallest number in the array [30,23,38,15,40,19,18,43,32,35,21].x = 30.14 9 5 3 2 12 1 17 20 422 10 6 11 25 16 13 24 31 7 830 23 38 15 40 19 18 43 32 35 2133 39 50 26 53 31 41 46 33 49 2745 44 52 37 54 53 48 47 34 514. Partition the array A using pivot x. Let x be kth element of A.Low = {22, 14, 10, 23, 9, 6, 5, 11, 26, 3, 15, 2, 25, 12, 19, 16, 18, 13, 1, 24, 17, 20, 4, 7, 21, 27, 8}High = {33, 45, 44, 39, 38, 52, 50, 37, 53, 40, 54, 55, 31, 48, 41, 43, 46, 47, 34, 31, 32, 33, 35, 49, 51}k = 285. Recursively find 10th element in Low.6 Running TimeLet T (n) be the running time for computing the kth smallest element of n numbers.Step 1 and 2: O(n) time. Step 3: T (dn5e) time. Step 4: O(n) time.Step 5: T (max(|L|, |H|)) time where L is the low side and H is the high side. We will show later that|L|, |H| ≤ 7n/10 + 6.Recurrence T (n) ≤ T (dn5e) + T (7n/10 + 6) + an.Simplified recurrence T (n) = T (n/5) + T (7n/10) + an.We pick the constant c = 10a and show by induction that T (n) ≤ cn.T (n) = T (n/5) + T (7n/10) + an≤ cn/5 + c(7n/10) + an= 9cn/10 + an= cn − cn/10 + an≤ cn.We show that |L| ≥ 3(dm2e − 2) where m is the number of columns.Then |L| ≥32m − 6 ≥310n − 6 since m = dn5e ≥n5.Then |H| ≤ n − |L| = 7n/10 + 6. Similarly |L| ≤ 7n/10 + 6.So, step 5 takes at most T (7n/10 + 6)
View Full Document
Unlocking...