作者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