引用Donald Knuth(通过维基百科的方式,因为我目前没有TAOCP的副本),比较次数的下限为6:
http://en.wikipedia.org/wiki/Selection_algorithm(向下滚动到标题为"Lower Bounds"的部分).
你的目标实际上是找到k个最低值,其中k是列表大小的一半,向上舍入,(因此,k = 3; n = 5),然后取最大值.将其插入到页面上的公式中,您会得到:
(5 - 3) + 1 + 1 + 2 = 6
Run Code Online (Sandbox Code Playgroud)
在这种情况下,所需比较的实际最小数量也是六.
如果您怀疑找到中位数的任务与找到k个最低值一样困难,您可以参考Knuth的TAoCP,第3卷,第5.3.3章后的练习#2.
| 归档时间: |
|
| 查看次数: |
7761 次 |
| 最近记录: |