計算機(jī)算法導(dǎo)論_第9章(參考版)
2024-10-22 10:17本頁面
【正文】 ● 。 else return RandomizedSelect(A, q+1, r, ik)。 if (i == k) then return A[q]。 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 i 1 other elements of A. ● How can we calculate order statistics? ● What is the running time? 4 11/12/2021 Minimum and Maximum 5 11/12/2021 Minimum and Maximum ● How many parisons are needed to find the minimum element in a set? The maximum? MINIMUM(A) 1 min ← A[1] 2 for i ← 2 to length[A] 3 do if min A[i] 4 then min ← A[i] 5 return min 6 11/12/2021 Simultaneous Minimum and Maximum ● Can we find the minimum and maximum with less than twice the cost? ● Yes: ■Walk through elements by pairs ○Compare each element in pair to the other ○Compare the largest to maximum, smallest to minimum ■Total cost: 3 parisons per 2 elements ≤3 ?n/2? = O(3n/2) 7 11/12/2021 Selection in expected linear time 8 11/12/2021 The Selection Proble
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1