Difference between revisions of "TADM2E 4.15"
(Recovering wiki) |
|||
| Line 7: | Line 7: | ||
Compare the first 3 elements and get rid of the smallest. Repeat this ( n - 2 ) times until we are done with all elements. Since it only takes at most 2 comparison to find the smallest element out of three, the total would be 2(n-2) = 2n-4 < 2n-3. | Compare the first 3 elements and get rid of the smallest. Repeat this ( n - 2 ) times until we are done with all elements. Since it only takes at most 2 comparison to find the smallest element out of three, the total would be 2(n-2) = 2n-4 < 2n-3. | ||
This methods also applies to b). | This methods also applies to b). | ||
| + | |||
| + | Potential alternate solution: | ||
| + | a) Build a max heap - O(n). Compare the two siblings at the second level of the tree and return the larger one (1 comparison). Therefore n + 1 assuming that element is not extracted | ||
| + | b) Build a max heap - O(n). Compare the two siblings at the second level and return the smaller one (1 comparison). Therefore n + 1 comparisons. | ||
Revision as of 14:41, 16 January 2015
a) First find the smallest element via n-1 comparisons, then remove the smallest from the array and call HEAPIFY (log n-1) and lastly extract-min. so totally n + log n -2.
b) The tournament algorithm is the best algorithm to find the 2nd largest element. In tournament algo we need to pair up 2 elements and then find the winner. then again do the same with the winners. Like a knockout football game. The second largest number can be any one in the list of numbers which lost to the winner. Check the winner in the losers group (lost to the best element). This can be done in n+log(n) time complexity.
Solution B for a):
Compare the first 3 elements and get rid of the smallest. Repeat this ( n - 2 ) times until we are done with all elements. Since it only takes at most 2 comparison to find the smallest element out of three, the total would be 2(n-2) = 2n-4 < 2n-3.
This methods also applies to b).
Potential alternate solution: a) Build a max heap - O(n). Compare the two siblings at the second level of the tree and return the larger one (1 comparison). Therefore n + 1 assuming that element is not extracted b) Build a max heap - O(n). Compare the two siblings at the second level and return the smaller one (1 comparison). Therefore n + 1 comparisons.
