計(jì)算機(jī)算法導(dǎo)論_第9章-預(yù)覽頁(yè)
【正文】 ? ● 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 Problem ● A more interesting problem is selection: finding the ith smallest element of a set ● We will show: ■ A practical randomized algorithm with O(n) expected running time ■ A cool algorithm of theoretical interest only with O(n) worstcase running time 9 11/12/2021 Randomized Selection ● Key idea: use partition() from quicksort ■ But, only need to examine one subarray ■ This savings shows up in running time: O(n) ● We will again use a slightly different partition q = RandomizedPartition(A, p, r) ? A[q] ? A[q] q p r 10 11/12/2021 Randomized Selection RandomizedSelect(A, p, r, i) if (p == r) then return A[p]。 if (i k) then return RandomizedSelect(A, p, q1, i)。 ● ,9
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1