Dec 26, 2008

Find max 2 numbers out of n numbers

Find max 2 numbers out of n numbers

Tournament algorithm:
Compare each two values on the list, take the bigger one, so we get a new list which is half of the original list; for the new list, compare each two values to take the bigger one, so we get a new list again. Repeat this operation until we get final number which is maximum value. Then for the values which were defeated by maximum value, we use of the same principle to get the final which is the second maximum value. The complexity is n-1+lgn-1

No comments:

Post a Comment