我正在浏览 this发布关于在最少的比较中找到获胜者和第二获胜者的复杂性。
该帖子说要进行 n + log(n) - 2
比较才能做到这一点。我知道需要进行 n-1
比较才能构建堆并获得获胜者。但除此之外,我无法理解需要额外的 log(n) - 1
比较才能找出第二个获胜者。
据我所知,还需要不断进行比较才能找出第二个获胜者,因为我们只需要从构造的堆中找到与获胜者竞争的两个最近的玩家,而这并不加起来log n - 1
。
最佳答案
一场有 n
名参与者的平衡单淘汰赛有 k = ceil(log2(n))
轮:每轮有一半的参与者被淘汰;只有最后两个会玩所有 k
轮。
在这个例子中,您只需要比较获胜者的最后两个对手的原因是只显示了 2 轮。在“现实世界”中,任何被最终冠军淘汰的球队都可能是第二好的(假设优势在任何两个玩家之间不变并且在所有玩家之间传递)。
因此,您必须比较输给冠军的 k
名选手。由于每次比较都会淘汰一名选手,因此您需要进行 k-1
比较才能找出剩下的银牌候选人。
关于algorithm - 寻找获胜者和第二名获胜者,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55305615/