Please Visit: http://ift.tt/1ajReyV
from Public RSS-Feed of Jeffery yuan. Created with the PIXELMECHANICS 'GPlusRSS-Webtool' at http://gplusrss.com http://ift.tt/1qzhksf
via LifeLong Community
algorithms - Lower bound for finding second largest element - Mathematics Stack Exchange
First find the maximum using a "tennis tournament" structure: first compare the nn elements in pairs, then compare the n/2n/2 "winners" in pairs, and so on. (Unpaired elements get a bye to the next round.) Since every element except the winner loses exactly once, this takes n−1n-1 comparisons. But now note that the second largest element must be one which lost to the winner, as it couldn't have been defeated by any other element. So you need to find the maximum among all the (up to) ⌈lgn⌉\lceil \lg n \rceil elements that were defeated by the winner, and finding this maximum can be done in ⌈lgn⌉−1\lceil \lg n \rceil - 1.
http://ift.tt/1qzhmAw
http://ift.tt/1qzhmQM
First find the maximum using a "tennis tournament" structure: first compare the nn elements in pairs, then compare the n/2n/2 "winners" in pairs, and so on. (Unpaired elements get a bye to the next round.) Since every element except the winner loses exactly once, this takes n−1n-1 comparisons. But now note that the second largest element must be one which lost to the winner, as it couldn't have been defeated by any other element. So you need to find the maximum among all the (up to) ⌈lgn⌉\lceil \lg n \rceil elements that were defeated by the winner, and finding this maximum can be done in ⌈lgn⌉−1\lceil \lg n \rceil - 1.
http://ift.tt/1qzhmAw
http://ift.tt/1qzhmQM
from Public RSS-Feed of Jeffery yuan. Created with the PIXELMECHANICS 'GPlusRSS-Webtool' at http://gplusrss.com http://ift.tt/1qzhksf
via LifeLong Community
No comments:
Post a Comment