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