計(jì)算機(jī)算法導(dǎo)論_第9章-wenkub
2022-11-03 10:17:26 本頁(yè)面
【正文】 ????????????122121221121222)(2)(1211112/12/The recurrence we started with Subs itute T(n) ? for T(k) Expand arithmetic series Multiply it out 21 11/12/2021 What happened here? Subtract c/2 What happened here? What happened here? What happened here? Randomized Selection ● Assume T(n) ? for sufficiently large c: The recurrence so far Multiply it out Rearrange the arithmetic we set out to prove ? ? ? ?? ?? ?? ?en o u g h ) b i g is c if(2424241221)(ncncnccnncnT??????????????????????????????????? 22 11/12/2021 Summary of randomized orderstatistic selection ? Works fast: linear expected time. ? Excellent algorithm in practice. ? But, the worst case is very bad: Θ(n2). 23 11/12/2021 Selection in worstcase linear time 24 11/12/2021 WorstCase LinearTime Selection ● What follows is a worstcase linear time algorithm, really of theoretical interest only ● Basic idea: ■ Generate a good partitioning element ■ Call this element x 25 11/12/2021 WorstCase LinearTime Selection ● The algorithm in words: 1. Divide n elements into groups of 5 2. Find median of each group (How? How long?) 3. Use Select() recursively to find median x of the ?n/5? medians 4. Partition the n elements around x. Let k = rank(x) 5. if (i == k) then return x if (i k) then use Select() recursively t
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1