问题描述
如何设置一般的最小比较数？
how do you setup minimum number of comparisons in general?
推荐答案
引用Donald Knuth我目前没有TAOCP的副本），比较次数的下限是六个：
To cite Donald Knuth (by way of Wikipedia, since I don't have my copy of TAOCP at the moment), the lower bound for the number of comparisons is six:
（向下滚动到标题为Lower Bounds的部分）。
http://en.wikipedia.org/wiki/Selection_algorithm (scroll down to the section entitled "Lower Bounds").
您的目标是有效地找到k个最小值，其中k是列表大小的一半，向上取整（因此，k = 3; n = 5），然后取最大的那些。将其插入页面上的公式，即可得到：
Your goal is, effectively, to find the k lowest values where k is half the size of the list, rounded up, (so, k = 3; n = 5) and then take the max of those. Plugging that into the formula there on the page, you get:
(5 - 3) + 1 + 1 + 2 = 6
在这种情况下，。
如果你不确定找到中位数的任务和找到k个最低值一样困难，你可以参考第5.3.3章后的Knuth的TAoCP，第3卷，练习＃2。
If you're in doubt that the task of finding the median is as hard as finding k lowest values, you may refer to Knuth's TAoCP, volume 3, excercise #2 after 5.3.3 chapter.
这篇关于给定5个数字，找到中值所需的最小比较数是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！