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

Question

我检查了关于 stackoverflow 的重复问题。这可能很接近:find number of tennis matches required

这是一个亚马逊面试问题。我想知道关键路径上的 Θ(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)。