作者LPH66 ((short)(-15074))
看板CSSE
標題Re: [問題] 不太懂在問什麼的演算法，解題好像 …
時間Wed May 5 05:44:05 2010
※ 引述《mqazz1 (無法顯示)》之銘言：
: 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
: 後面就翻不太出來在表達什麼..
: 想請問一下這題在問什麼呢?
做法上一篇有人說了, 這裡寫一下我流題目翻譯:
證明不存在比較型排序法，其執行時間在所有長度 n 的 n! 種輸入中
至少有一半是線性的。若將一半改成 1/n 如何？改成 1/2^n 又如何？
這樣再配合上一篇應該就能搞懂這題了...
--
**** 說:
不要期望一個精神力差不多已經見底的人阿Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
※ 編輯: LPH66 來自: 140.112.28.92 (05/05 05:44)