给出5个号码，什么是找到中值需要比较的最小数目？ [英] given 5 numbers, what is the minimum number of comparisons needed to find the median?

问题描述

你怎么一般比较设置最低数量？

how do you setup minimum number of comparisons in general?

推荐答案

要举高德纳（维基百科的方式，因为我没有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:

http://en.wikipedia.org/wiki/Selection%5Falgorithm （向下滚动到名为下界）的部分。

http://en.wikipedia.org/wiki/Selection%5Falgorithm (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

在这种情况下，实际最小数目需要比较的结果也是6 。

如果你是在怀疑，寻找位数的任务是硬如发现ķ最低值，你可能5.3.3章后参考Knuth的TAOCP，第3卷，锻炼; Tibial＃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个号码，什么是找到中值需要比较的最小数目？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！