查找最强人算法

假设关系“更强”是可传递的。。。每次决斗只会让一个人失去考虑。因此,你找不到最强壮的人 n-1 决斗。

如果我们假设强度是 weakly-ordered ,这与假设“如果A比B强,B比C强,C永远不会比A强”对于某些A,B,C是一样的。也就是说,我们可以通过传递假设,如果“A比B强,B比C强”,那么“A也比C强”。

因此,我们的弱序竞争将包括每个邻居将自己与他们的邻居进行比较。这消除了 参赛者仅在一轮(N/2比较)。我们重复这个力量测试,直到只剩下一个人:

   O   O  O   O  O   O
    \ /    \ /    \ /
     O      O      O
      \    /       |
       \  /        |
         O         O
          \       /
           \     /
            \   /
              O

该算法的时间复杂度为O(N),“轮数”为下限(log_2(N))。在我的示例中,N=6,而floor(log_2(6))=2。这是O(N),因为我们遇到了许多以N/2、N/4、N/8的形式出现的对峙。。。然后1,留给我们求和N/2+N/4+N/8+…+1,或N/(2)的总和 )对于从0到地板的i(log_2(N)),由于我们知道地板(log_2(N))小于无穷大,我们可以放心地说结果小于或等于 summation of the common geometric series 乘以N,即N。因此O(N)

)(因为比较的数量是 Triangular Numbers 减n):

• 2面对3和4(2面对面,2已经面对1)
• 3面对4(1面对,已经面对1和2)

所以我们有一个对峙的总和,比如(n-1)+(n-2)+…+1.