※ 引述《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! 種可能的排序結果.
沒搞錯的話, 應該是可以把 comparison sort 那個經典的下界證法搬過來用...
我們把每一種順序貼上一個標籤, 這個標籤是我們考慮的演算法吃了該順序的輸入時,
依序所做的所有天秤量測結果 (每次量測結果為左或右)...
如果 n! 種順序當中, 有若干種是可以被此演算法正確排序的, 那麼我們把這幾種順序
放在一個集合 S 裡面, 我們可以證明 S 裡面任兩種順序不可能被貼上相同標籤 (標籤
之意義如上一段)... 否則該兩種順序就不可能都被正確排序...
又, 假設此一演算法在餵了 S 裡面任一種順序後, 皆頂多做 t 次比較, 那麼 S 裡面
每種順序的標籤總數就不能超過 2^0 + 2^1 + ... + 2^t, 這是因為 <=t 次的量測結果
頂多有這麼多種... 然而我們上一段提到 S 裡面任兩種順序都具有相異標籤, 因此
|S| <= 2^0 + 2^1 + ... + 2^t,
在這題的設定中, t 是設成 O(n), 所以 |S| = 2^{O(n)}...
那我們只要檢查一下 n!/2, n!/n, n!/2^n 是不是 2^{O(n)}, 就可以回答這題了...
由 Stirling formula 可以知道 n!=2^{Θ(n log n)}... 所以三個答案都是 no...
當然如果你要考慮 randomized comparison sort 就需要有點不太一樣的分析了...
--
希望沒搞錯什麼囉... 我承認我是來賺 p 幣的... XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.124.101.74