Algorithms Illuminated (Roughgarden) - Problem 1.5 : Optimal Number of Comparisons to Find Second-Largest Numberjeongtaebang 2017.10.21 00:19
Find a maximum in a tournament style. The number of comparisons is equal to the number of matches that occur. For n competitors, there will be n - 1 matches until we get a champion (the max).
Figure 1 : Tournament with n = 8
We can see that the number of comparisons is n - 1 = 7.
We can use the tournament record (tree) to find the competitors that lost to the champion and build the list. In the example above it is <1, 5, 7>.
The second-largest element must have lost to the champion at some point during the tournament.
Suppose, to the contrary, it lost to some element other than the champion. Then there exists an element greater than the second-largest, which is the champion. CONTRADICTION
What is the length of this list? It is the height of the tree, which is . Using step 1 again on this list, we can find the second-largest in comparisons.
In total, we need at most comparisons.
1. Implement with Java
2. Generalize to finding the ksmallest element in the array with math proof. Is the bound tight (can we establish a lower bound)?
'Comp Sci > Problem Solving' 카테고리의 다른 글
- Two Pointer
- Proof of Correctness