July 29, 2016
Top k values in the
array - review the following article:
http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
1. sorting the array O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics
7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case
http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array. Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...
7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).
7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.
http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
1. sorting the array O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics
7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case
http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array. Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...
7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).
7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.
No comments:
Post a Comment