查找锦标赛比赛列表中的优胜者

Question

我在重叠问题上进行了检查。这可能是关闭的：find number of tennis matches required

这是亚马逊的面试问题。我想知道对于'p'玩家来说，关键路径上的Θ（log 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玩家减少球员requries P-1比赛..

如果您正在安排比赛的最大数量的同时，有一个球员可以在参加只有一个匹配的约束时间，并且想要知道haw需要多次回合，那就是天花板（log p）。