algorithm - 寻找获胜者和第二名获胜者

Question

我正在浏览 this发布关于在最少的比较中找到获胜者和第二获胜者的复杂性。

该帖子说要进行 n + log(n) - 2 比较才能做到这一点。我知道需要进行 n-1 比较才能构建堆并获得获胜者。但除此之外，我无法理解需要额外的 log(n) - 1 比较才能找出第二个获胜者。

据我所知，还需要不断进行比较才能找出第二个获胜者，因为我们只需要从构造的堆中找到与获胜者竞争的两个最近的玩家，而这并不加起来log n - 1。

Answer 1

一场有 n 名参与者的平衡单淘汰赛有 k = ceil(log2(n)) 轮:每轮有一半的参与者被淘汰；只有最后两个会玩所有 k 轮。

在这个例子中，您只需要比较获胜者的最后两个对手的原因是只显示了 2 轮。在“现实世界”中，任何被最终冠军淘汰的球队都可能是第二好的(假设优势在任何两个玩家之间不变并且在所有玩家之间传递)。

因此，您必须比较输给冠军的 k 名选手。由于每次比较都会淘汰一名选手，因此您需要进行 k-1 比较才能找出剩下的银牌候选人。