给定 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(通过 Wikipedia，因为我目前没有我的 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(向下滚动到标题为下界"的部分).

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 个最小值一样困难，您可以参考 Knuth 的 TAoCP，第 3 卷，第 5.3.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屋！