0

我检查了关于 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

.

4

1 回答 1

4

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

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

于 2013-03-16T18:00:17.217 回答