k******r
发帖数: 2300 | 1 Suppose there is 100 game players. What is the number of games that will be
played to find out the final winner? Require time complexity should be
CONSTANT. |
b********n
发帖数: 609 | 2 你说你这题的主要精神是什么吧，2人对决，100人比2场，1万人比5场。有这好算法你能
得诺贝尔数学奖了。
要
【在 k******r 的大作中提到】
: Suppose there is 100 game players. What is the number of games that will be
: played to find out the final winner? Require time complexity should be
: CONSTANT.
|
N********n
发帖数: 8363 | 3 Is it possible?
【在 k******r 的大作中提到】
: Suppose there is 100 game players. What is the number of games that will be
: played to find out the final winner? Require time complexity should be
: CONSTANT.
|
t*******l
发帖数: 3662 | 4 那简单啊，把把每场比赛时间用（n-1）normalize 一下不就行了。
人
算
的
【在 k******r 的大作中提到】
: Suppose there is 100 game players. What is the number of games that will be
: played to find out the final winner? Require time complexity should be
: CONSTANT.
|
g****c
发帖数: 299 | 5 只有一个比赛场地吗？问题没法给具体的答案，只能给个idea。
一对一淘汰的话，就建个blance binary tree，log(2)100=7 log(2)10000=14
也就是你要的数量级，不知道这道题是出至何处，哪门课？要你想多深。
【在 k******r 的大作中提到】
: Suppose there is 100 game players. What is the number of games that will be
: played to find out the final winner? Require time complexity should be
: CONSTANT.
|
p*u
发帖数: 2454 | 6 I finally think OP was asking for a parallel algorithm. |
c*****t
发帖数: 1879 | 7 Constant time to find the result? It would just be an formula to calculate
the # of comparisons to find the result. It's just like you can use
Fib math formula to directly calculate the N-th number in constant time, or
use linear algorithm to find the result.
Algorithm wise, the problem can be solved in linear time using N-1
comparisons. If using parallelism, if I remember correctly, ln(N) time is
required, but overhead is large. You can think it as merge sort to
distribute the comparison ta |
c**r
发帖数: 10001 | 8 if it's constant time, is it doable?
【在 c*****t 的大作中提到】
: Constant time to find the result? It would just be an formula to calculate
: the # of comparisons to find the result. It's just like you can use
: Fib math formula to directly calculate the N-th number in constant time, or
: use linear algorithm to find the result.
: Algorithm wise, the problem can be solved in linear time using N-1
: comparisons. If using parallelism, if I remember correctly, ln(N) time is
: required, but overhead is large. You can think it as merge sort to
: distribute the comparison ta
|
