計算機算法導(dǎo)論_第9章(完整版)
【正文】 stitute T(n) = Combine fractions Express in desired formWhat we set out to prove 36 11/12/2021 LinearTime Median Selection ● Given a “black box” O(n) median algorithm, what can we do? ■ ith order statistic: ○ Find median x ○ Partition input around x ○ if (i ? (n+1)/2) recursively find ith element of first half ○ else find (i (n+1)/2)th element in second half ○ T(n) = T(n/2) + O(n) = O(n) ■ Can you think of an application to sorting? 37 11/12/2021 WorstCase LinearTime Selection ● Intuitively: ■ Work at each level is a constant fraction (19/20) smaller ○ Geometric progression! 38 11/12/2021 LinearTime Median Selection ● Worstcase O(n lg n) quicksort ■ Find median x and partition around it ■ Recursively quicksort two halves ■ T(n) = 2T(n/2) + O(n) = O(n lg n) 39 11/12/2021 The End Exercises ● 。 q = RandomizedPartition(A, p, r) k = q p + 1。 ● 。 1 11/12/2021 Introduction to Algorithms 9 Medians and Order Statistics 2 11/12/2021 Order Statistics ● The ith order statistic in a set of n elements is the ith smallest element ● The minimum is thus the 1st order statistic ● The maximum is the nth order statistic ● The median is the n/2 order statistic ■ If n is even, there are 2 medians 3 11/12/2021 Selection Problem Input: 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1