※ 引述《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