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