查找錦標賽比賽列表中的優勝者

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）。