寻找最强者算法

Question

我想知道如何比我想出的更好地解决以下问题。基本上你有 n 个人，你想通过让他们扳手腕来找出这 n 个人中谁最强壮。我想出了如何用 n-1 决斗来解决这个问题，但是还有其他解决方案吗，例如 log(n) og 3n/2?

谢谢。

Answer 1

假设关系 'stronger' 是可传递的...每次决斗都会从考虑中删除一个人。因此，你找不到少于n-1次对决的最强者。

Answer 2

如果我们假设强度是weakly-ordered，那么它与假设A，B，C的"If A is strong than B, and B is stronger than C, C is never stronger than A"是一样的。也就是说，我们可以传递地假设如果"A is stronger than B"，以及 "B is stronger than C"，然后还有 "A is stronger than C"。

因此，我们的弱排序竞赛将包括每个邻居将自己与邻居进行比较。这仅在一轮（N/2 比较）中就淘汰了一半名参赛者。我们重复这个力量测试，直到只剩下一个人：

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

这样一个算法的时间复杂度是O(N)，"rounds"的个数是floor(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ⁱ) 对于 i 从 0 到 floor(log_2(N))，因为我们知道 floor(log_2(N)) 小于无穷大我们可以安全地说结果小于或等于 summation of the common geometric series 乘以 N，即 N。因此 O(N)

如果我们不能假设弱排序，那么我们最终会遇到 A 可能打败 B，B 可能打败 C，但 C 可以打败 A 的情况。没有办法 "sort" 这样的集合按照从强到弱的顺序，所以我们不得不让每个人都对战，这样我们就可以计算出 Wins/Losses 记录。然后我们可以通过他们的胜利来排序我们的竞争对手。这样计算"all pairs"的算法是O(N²)（因为比较的次数是Triangular Numbers减去n）：

1 对阵 2、3、4（3 次对决）
2 对决 3 和 4（2 对决，2 已经对决 1）
3 对阵 4（1 对阵，已经对阵 1 和 2）

所以我们得到了对峙的总和，例如 (n-1) + (n-2) + ... + 1

寻找最强者算法

Find the strongest person algorithm

algorithm

pseudocode

array-algorithms