algorithm - given 5 numbers, what is the minimum number of comparisons needed to find the median?

Question

how do you setup minimum number of comparisons in general?

Answer 1

引用 Donald Knuth（通过 Wikipedia，因为我目前没有我的 TAOCP 副本），比较次数的下限是 6：

http://en.wikipedia.org/wiki/Selection_algorithm（向下滚动到标题为“下限”的部分）。

实际上，您的目标是找到 k 个最小值，其中 k 是列表大小的一半，四舍五入（因此，k = 3；n = 5），然后取其中的最大值。将其插入页面上的公式中，您将获得：

(5 - 3) + 1 + 1 + 2 = 6

在这种情况下，实际所需的最小比较次数也是 6。

如果您怀疑求中位数的任务与求 k 个最小值一样困难，您可以参考 Knuth 的 TAoCP，第 3 卷，第 5.3.3 章后的练习 #2。

Answer 2

Donald Knuth 的The Art of Computer Programming的第3 卷中有很多关于此的材料，在第 5.3.3 节，Minimum-Comparison Selection中，其中更一般的问题是选择第t个最大的比较所需的最小比较次数。考虑n 个值。（这个值用V _t (n)表示）。

Knuth 给出了 V t (n) 的n - _t + (t-1)⌈lg(n + 2 - t)⌉的上限，这是通过首先通过锦标赛系统确定n - t + 2的最大元素来实现的，删除这个（因为它不可能是第t大的）并用剩下的元素之一替换它，继续这个过程直到所有元素都成为这个过程的一部分，然后这个阶段的最大元素是第t大的原始集。在这种情况下，n = 5和t = 3，所以这个公式给出的上限是 6 次比较。

Knuth 提到，当n ≤ 6时，这个上限是准确的，因此适用于这种情况。一般来说，我的理解是，没有找到用于选择（和排序）的最小比较算法的一般程序，并且增加n值的记录通常使用特殊技巧，这些技巧通常不适用于较大的值，或者只是被击败当n增加时的其他技巧。