9-1 Largest $i$ numbers in sorted order

Given a set of \(n\) numbers, we wish to find the \(i\) largest in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of \(n\) and \(i\) .

a. Sort the numbers, and list the \(i\) largest.

b. Build a max-priority queue from the numbers, and call \(\text{EXTRACT-MAX}\) \(i\) times.

c. Use an order-statistic algorithm to find the \(i\)th largest number, partition around that number, and sort the \(i\) largest numbers.

a. The running time of sorting the numbers is \(O(n\lg n)\), and the running time of listing the \(i\) largest is \(O(i)\). Therefore, the total running time is \(O(n\lg n + i)\).

b. The running time of building a max-priority queue (using a heap) from the numbers is \(O(n)\), and the running time of each call \(\text{EXTRACT-MAX}\) is \(O(\lg n)\). Therefore, the total running time is \(O(n + i\lg n)\).

c. The running time of finding and partitioning around the \(i\)th largest number is \(O(n)\), and the running time of sorting the \(i\) largest numbers is \(O(i\lg i)\). Therefore, the total running time is \(O(n + i\lg i)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用