計(jì)算機(jī)算法導(dǎo)論_第9章-資料下載頁(yè)
2024-10-19 10:17本頁(yè)面
【正文】 How many elements are ? x? ■ At least 3 ?n/10 ? elements ● For large n, 3 ?n/10 ? ? n/4 (How large?) ● So at least n/4 elements ? x ● Similarly: at least n/4 elements ? x 34 11/12/2021 WorstCase LinearTime Selection 35 11/12/2021 WorstCase LinearTime Selection ● Thus after partitioning around x, step 5 will call Select() on at most 3n/4 elements ● The recurrence is therefore: ? ?? ? ? ? ? ?? ? ? ? ? ?? ?? ?en o u g h b i g is if20)(2021)(435435435)(cnnnnnTnTnnTnTnT??????????????????????? ??? ??? ??? ??? ?n/5 ? ? n/5Substitute T(n) = Combine fractions Express in desired formWhat we set out to prove 36 11/12/2021 LinearTime Median Selection ● Given a “black box” O(n) median algorithm, what can we do? ■ ith order statistic: ○ Find median x ○ Partition input around x ○ if (i ? (n+1)/2) recursively find ith element of first half ○ else find (i (n+1)/2)th element in second half ○ T(n) = T(n/2) + O(n) = O(n) ■ Can you think of an application to sorting? 37 11/12/2021 WorstCase LinearTime Selection ● Intuitively: ■ Work at each level is a constant fraction (19/20) smaller ○ Geometric progression! 38 11/12/2021 LinearTime Median Selection ● Worstcase O(n lg n) quicksort ■ Find median x and partition around it ■ Recursively quicksort two halves ■ T(n) = 2T(n/2) + O(n) = O(n lg n) 39 11/12/2021 The End Exercises ● 。 ● 。 ● ,9
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1