計(jì)算機(jī)算法導(dǎo)論_第9章-在線瀏覽
2024-12-06 10:17本頁(yè)面
【正文】 near 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 to find ith smallest element in first partition else (i k) use Select() recursively to find (ik)th smallest element in last partition 26 11/12/2021 Choosing the pivot 27 11/12/2021 Choosing the pivot 28 11/12/2021 Choosing the pivot 29 11/12/2021 Choosing the pivot 30 11/12/2021 Analysis 31 11/12/2021 Analysis(Assume all elements are distinct.) 32 11/12/2021 Analysis(Assume all elements are distinct.) 33 11/12/2021 WorstCase LinearTime Selection ● How many of the 5element medians are ? x? ■ At least 1/2 of the medians = ??n/5? / 2? = ?n/1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1