algorithm - 在锦标赛比赛列表中查找获胜者

Question

我检查了关于 stackoverflow 的重复问题。这可能很接近：查找所需的网球比赛数量

这是一个亚马逊面试问题。我想知道关键路径上的 Θ(log p) 操作是否是“p”玩家的正确答案（与锦标赛障碍算法-> John Mellor-Crummey 相同）。

例如，我们有 4 名玩家 1、2、3、4。我们可以安排以下比赛：

 1)  Between (1 & 2)

 2)  Between (3 & 4) 

 3) organize the third match between winners of these two matches. 

同样，对于 5（奇数）名玩家，我们可以安排以下比赛：

 1) (1 & 2) and (3 & 4) 

 2) Winner from (1&2) OR winner from (3&4) against 5

 3) Winner between winner of not chosen group and winner from previous match

.

Answer 1

每场比赛只淘汰一名球员。要将p玩家减少到1玩家需要p-1匹配..

如果您要同时安排最大数量的比赛，并且球员一次只能参加一场比赛，并且想知道需要多少轮比赛，那就是上限（log p）。