给定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?

推荐答案

引用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:

http://en.wikipedia.org/wiki/Selection_algorithm （向下滚动到标题为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个数字，找到中值所需的最小比较数是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！