計算機(jī)算法導(dǎo)論_第9章-文庫吧資料
2024-10-25 10:17本頁面
【正文】 m ● 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]。 q = RandomizedPartition(A, p, r) k = q p + 1。 if (i k) then return RandomizedSelect(A, p, q1, i)。 ? A[q] ? A[q] k q p r 11 11/12/2021 Randomized Selection ● Analyzing RandomizedSelect() ■ Worst case: partition always 0:n1 T(n) = T(n1) + O(n) = ??? = O(n2) (arithmetic series) ○ No better than sorting! ■ “Best” case: suppose a 9:1 partition T(n) = T(9n/10) + O(n) = ??? = O(n) (Master Theorem, case 3) ○ Better than sorting! ○ What if this had been a 99:1 split? 12 11/12/2021 Randomized Selection 13 11/12/2021 Randomized Selection 14 11/12/2021 Calculating expectation 15 11/12/2021 Calculating expectation 16 11/12/2021 Calculating expectation 17
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1