[問題] 不太懂在問什麼的演算法，解題好像 …

看板CSSE作者 (無法顯示)時間14年前 (2010/05/01 22:59), 編輯推噓3(3推 0噓 4→)
留言7則, 3人參與, 最新討論串1/3 (看更多)
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
→
05/02 01:27, , 1F
n!/2是絕對的 那麼 1/n 呢? 1/2^n(2的n次方)呢?
05/02 01:27, 1F
→
05/02 01:28, , 2F
以上為 無責推文XD
05/02 01:28, 2F
推
05/02 04:13, , 3F
亂翻一下:試證對於長度為n,筆數至少為n!/2的資料,不存在一
05/02 04:13, 3F
→
05/02 04:15, , 4F
個時間複雜度為O(n)的比較資料的演算法? 承上,若筆數為原本
05/02 04:15, 4F
→
05/02 04:16, , 5F
原本的(1/n)?若筆數為原本的1/2^n?
05/02 04:16, 5F
推
05/03 22:35, , 6F
應該是一樓那樣　n!/2是給定的條件　證後面兩個
05/03 22:35, 6F
推
05/05 14:14, , 7F
糟糕誤解了 抱歉@@||
05/05 14:14, 7F
‣ 更多 mqazz1 的文章
文章代碼(AID): #1Bt47Ube (CSSE)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 mqazz1 的文章
文章代碼(AID): #1Bt47Ube (CSSE)