An algorithm question. - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

An algorithm question.

An algorithm question.# Programming - 葵花宝典

k*r2006-01-11 08:01

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*n2006-01-11 08:01

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*n2006-01-11 08:01

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*l2006-01-11 08:01

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*c2006-01-11 08:01

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*u2006-01-11 08:01

6 楼

I finally think OP was asking for a parallel algorithm.

c*t2006-01-11 08:01

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*r2006-01-11 08:01

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