Dec 28, 2008

Give efficient algorithms for finding the largest k values (in order) out of

Give efficient algorithms for finding the largest k values (in order) out of
a set of n, using comparisons only (e.g. no hashing), in the case where:
(a) k = 3 (b) k = n/2; (c) k = log(n).
(You can use a different algorithm for each case.)
State the asymptotic worst-case running time of your algorithms.
For (a), we use tournament algorithm, which has done this by n-1+logn-1+logn-2+logn-1, O(n+klogn-m) comparison
For (b), we use selection algorithm, which has done this by O(n) if the pivot is the median of the median of the array
For (c), we use minheap, which has done this by O(nlogk), notice when we heapify the min heap, do comparison on two child nodes first, and then swap the parent node with the smaller one, that is where the logk come from

No comments:

Post a Comment