比賽決定排名

Question

N人蔘加比賽由很多回合組成。 在一輪中，M人可以參加比賽。我們只記錄他們的等級，不記錄他們的分數。 我們需要確定K個最快人選的最低迴合數是多少？ 這似乎是一個經典問題。如果你知道，請告訴我。謝謝！

Answer 1

讓R*表示R的最佳值，即使用的回合數。很容易證明，如果N=K*M和M=K*K然後R* = K+1。示例：K=7, M=49, N=341：運行帶有非重疊組的輪次K=7。 K是可觸及每個項目的最小回合數，但對於任何給定項目，回合數不能證明它是或不在頂部K.因此R* > K爲N=K^3和M=K^2的情況。現在再運行一輪，每輪前7名選出本輪的前7名。

我不知道作爲一個「典型問題」所陳述的問題，並認爲我的例子說明這個問題是從分類型爲O（n LN n）的複雜性問題不同，並與median or tournament algorithms或selection algorithms更一致。當然，彙集測試和稱量算法有大量文獻，解決這些問題的一些推理適用於此，但其具體方法卻不適用。