作者mqazz1 (无法显示)
看板CSSE
标题[问题] 不太懂题目在问什麽的演算法，解题好像也蛮难的
时间Sat May 1 22:59:39 2010
Show that there is no comparison whose running time is linear for at least
half of the n! inputs of length n. What about a fraction of 1/n of the inputs
of length n? What about a fraction 1/2^n?
我自己的翻译是:
秀出没有比较它的执行时间式线性的，它至少有 n! 一半的输入，长度为 n
後面就翻不太出来在表达什麽..
想请问一下这题在问什麽呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.26.91
1F：→ justben:n!/2是绝对的 那麽 1/n 呢? 1/2^n(2的n次方)呢? 05/02 01:27
2F：→ justben:以上为 无责推文XD 05/02 01:28
3F：推 bob123:乱翻一下:试证对於长度为n,笔数至少为n!/2的资料,不存在一 05/02 04:13
4F：→ bob123:个时间复杂度为O(n)的比较资料的演算法? 承上,若笔数为原本 05/02 04:15
5F：→ bob123:原本的(1/n)?若笔数为原本的1/2^n? 05/02 04:16
6F：推 hilorrk:应该是一楼那样 n!/2是给定的条件 证後面两个 05/03 22:35
7F：推 bob123:糟糕误解了 抱歉@@|| 05/05 14:14