麻省理工学院：《算法导论》（英文版） Lecture 6 Prof erik demaine

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 6 Prof erik demaine

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 6 Prof. Erik Demaine

Order statistics Select the ith smallest of n elements( the element with rank i) i=l: minimum i-n.mimu i=L(n+1)2] or[(n+1)/2 median Naive algorithm: Sort and index ith element Worst-case running time=o(n Ig n)+O(1) o(n Ig n) using merge sort or heapsort(not quicksort) o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.2

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.2 Order statistics Select the ith smallest of n elements (the element with rank i). • i = 1: minimum; • i = n: maximum; • i = (n+1)/2 or (n+1)/2: median. Naive algorithm: Sort and index ith element. Worst-case running time = Θ(n lg n) + Θ(1) = Θ(n lg n), using merge sort or heapsort (not quicksort)

randomized divide-and conquer algorithm RAND-SELECT(A, p, g, i) bith smallest of.. g if p=g then return alp rk=rank(A[rD if i=k then return a[rI if i<k then return RaNd-seleCt(A, p, r-1, i) else return RAND-SELECT(A, r+1, g, i-k) ≤A[ ≥A[r o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.3

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.3 Randomized divide-and￾conquer algorithm RAND-SELECT(A, p, q, i) ⊳ ith smallest of A[p . . q] if p = q then return A[p] r ← RAND-PARTITION(A, p, q) k ← r – p + 1 ⊳ k = rank(A[r]) if i = k then return A[r] if i < k then return RAND-SELECT(A, p, r – 1, i) else return RAND-SELECT(A, r + 1, q, i – k ) ≤≤AA[r] [r] ≥≥AA[r] [r] p q r k

Example Select the i=th smallest 61013583211i=7 pivot Partition 253681310111k=4 Select the 7-4=3rd smallest recursively o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6. 4

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.4 Example pivot 66 1010 1313 55 88 33 22 1111 i = 7 k = 4 Select the 7 – 4 = 3rd smallest recursively. Select the i = 7th smallest: 22 55 33 66 88 1313 1010 1111 Partition:

Intuition for analysis (All our analyses today assume that all elements are distinct Lucky 7(n)=7(97/10)+e(m)nog091=n0=1 (n) case 3 Unlucky: 7(n)=7(n-1)+(n arithmetic series ⊙(n2) Worse than sorting o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.5

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.5 Intuition for analysis Lucky: 1 log10/ 91 0 n = n = CASE 3 T(n) = T(9n/10) + Θ(n) = Θ(n) Unlucky: T(n) = T(n – 1) + Θ(n) = Θ(n2) arithmetic series Worse than sorting! (All our analyses today assume that all elements are distinct.)

Analysis of expected time The analysis follows that of randomized quicksort, but it's a little different Let T(n)=the random variable for the running time of RaNd-SELECT on an input of size n assuming random numbers are independent For k=01. n-1. define the indicator random variable ks 1 if PartItion generates a k: n-k-1 sp pl 0 otherwise o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.6

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.6 Analysis of expected time Let T(n) = the random variable for the running time of RAND-SELECT on an input of size n, assuming random numbers are independent. For k = 0, 1, …, n–1, define the indicator random variable Xk = 1 if PARTITION generates a k : n–k–1 split, 0 otherwise. The analysis follows that of randomized quicksort, but it’s a little different

Analysis(continued) To obtain an upper bound, assume that the ith element al ways falls in the larger side of the partition T(max(0, n-1)+o(n) if0: n-1 split T(max1, n-2))+o(n) if 1: n-2 split T(max(n-1,0)+o(n ifn-1: 0 split 2X(T(maxk, n-k-1)+0(n) k=0 o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.7

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.7 Analysis (continued) T(n) = T(max{0, n–1}) + Θ(n) if 0 : n–1 split, T(max{1, n–2}) + Θ(n) if 1 : n–2 split, M T(max{n–1, 0}) + Θ(n) if n–1 : 0 split, ∑ ( ) − = = − − + Θ 1 0 (max{ , 1}) ( ) n k Xk T k n k n . To obtain an upper bound, assume that the ith element always falls in the larger side of the partition:

Calculating expectation E[T(m)=E∑Xk(T(max体.n-k-1)+(n) Take expectations of both sides o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.8

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.8 Calculating expectation ( )  = ∑ − − + Θ −=10 [ ( )] (max{ , 1}) ( ) nk E T n E Xk T k n k n Take expectations of both sides

Calculating expectation E[T(n)=E 2Xk(T(max(k,n-k-1)+O(n) k=0 k=o k((max(k, n-k-1)+O(n)7 ∑E[X Linearity of expectation o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.9

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.9 Calculating expectation ( ) ∑ [ ] ( ) ∑ − = − = = − − + Θ   = − − + Θ 1 0 1 0 (max{ , 1}) ( ) [ ( )] (max{ , 1}) ( ) n k k n k k E X T k n k n E T n E X T k n k n Linearity of expectation

Calculating expectation E[T(m)=E∑x(7(max伙k,n=k-1)+(m) k=0 XELXk(T(max(k, n-k-1))+O(n) k=0 ZELXK.E[T(max k, n-k-1))+O(n) Independence of X, from other random choices o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.10

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.10 Calculating expectation ( ) [ ] ( ) ∑ [ ][ ] ∑ ∑ − = − = − = = ⋅ − − + Θ = − − + Θ   = − − + Θ 1 0 1 0 1 0 (max{ , 1}) ( ) (max{ , 1}) ( ) [ ( )] (max{ , 1}) ( ) n k k n k k n k k E X E T k n k n E X T k n k n E T n E X T k n k n Independence of Xk from other random choices