티스토리 뷰



Step 1: 

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.

In general, 






Step 2:

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.




TODO:

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)?


https://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-number-of-comparisons

https://math.stackexchange.com/questions/1601/lower-bound-for-finding-second-largest-element

http://jeffe.cs.illinois.edu/teaching/497/02-selection.pdf


댓글
댓글쓰기 폼