資料結構›Ch7 搜尋與排序第 51 題／共 76 題
51. Selection Algorithm、Median of Medians
#DS-07-051易Selection AlgorithmMedian of Medians
- Given n integers, the problem of searching for the k'th largest integer among the n integers is called "selection problem". Selection problems can be solved in linear time. Typical implementation starts with partitioning the n integers into groups. Then we solve a sequence of median finding (selection problem again) from integers of smaller problem size. Finally we can drop out more than a quarter of the n integers. The next iteration is to deal with a selection problem of size less than . Thus linear time is achieved. Which of the following statement(s) is(are) correct?
📄 交大110
▤完整推導請見《WH 資工筆記 · 資料結構》Ch7 搜尋與排序