问题标签 [median-of-medians]

除了中位数算法之外，还有其他方法可以在最坏情况 O(n) 时间内进行 k 选择吗？实施中位数是否有意义？我的意思是，性能优势是否足以满足实际用途？

我在网上搜索并访问了中位数算法的 wiki 页面。但似乎找不到我的问题的明确陈述：

如果一个人有一个非常大的整数列表（大小为 TB），并且想要以分布式方式找到该列表的中位数，则将列表分解为不同大小的子列表（或相等并不重要），然后继续计算那些较小子列表的中位数，然后计算这些中位数的中位数导致原始大列表的中位数？

此外，对于任何第 k 个统计数据，此语句是否也正确？我会对这个领域的研究等链接感兴趣。

我想了解以下示例中的“中位数”算法：

我们有 45 个不同的数字，分为 9 组，每组 5 个元素。

1. 第一步是对每个组进行排序（在这种情况下，它们已经排序）

2. 第二步递归，找到中位数（50 45 40 35 30 25 20 15 10）的“真实”中位数，即集合将分为 2 组：

   对这两组进行排序

   /li>

中位数是 40 和 15（如果数字是偶数，我们取左中位数）所以返回值是 15 但是中位数 ( 50 45 40 35 30 25 20 15 10) 的“真实”中位数是 30，此外还有 5 个小于 15 的元素远小于 30维基百科中提到的 45 个中的百分比

所以T(n) <= T(n/5) + T(7n/10) + O(n)失败了。

顺便说一句，在 Wikipedia 示例中，我得到的递归结果为 36。但是，真正的中位数是 47。

所以，我认为在某些情况下，这种递归可能不会返回真正的中位数。我想了解我的错误在哪里。

我直接从书中复制了这个算法，但是在“这里的错误！！！！！！”处不断收到 ArrayIndexOutOfBoundsException 部分...对于 T[i] = ...

这让我发疯，我需要完成这件事......有人可以建议我如何解决这个问题吗？由于翻译书中的算法，我还评论了其他潜在的错误......

去上班了，一会儿回来。非常感谢您的帮助..

这是通过将数组分成5组来实现中位数的伪代码

我有两个问题：

1. 第一个与分区代码有关，这里我们只给出数组及其边界，没有指示枢轴元素，那么这个分区代码应该是什么样子？我们应该选择枢轴索引和枢轴元素为：

   还是应该是随机选择？

2. 如何输出选定的中位数？

通常语言无关紧要，但如果示例用 C++ 显示就更好了。

我最近在分析了第k个最小元素算法之后写了一个程序，首先没有重复的情况。

但是，现在我想分析预期的渐近运行时间，以便在完全j重复时找到数组的中位数。我没有为此修改我的代码，因此由于j重复，性能会有所降低。

我不知道如何开始？谁能指出我这样的重复关系？

我推导出以下内容，其中 n 是输入数组的大小

但我很不清楚如何处理涉及的重复键。

谢谢

该Median of medians方法在类型划分算法中非常流行，quicksort可以产生相当好的枢轴，从而均匀地划分数组。其逻辑在 Wikipedia 中给出为：

选择的枢轴小于和大于中位数列表中元素的一半，每半数约为 n/10 个元素 (1/2 * (n/5))。这些元素中的每一个都是 5 的中位数，使其小于块外的 2 个其他元素和大于 2 个其他元素。因此，主元小于块外的 3(n/10) 个元素，大于块外的另外 3(n/10) 个元素。因此，所选中值将元素拆分为 30%/70% 和 70%/30% 之间的某个位置，这确保了算法的最坏情况线性行为。

有人可以为我解释清楚一点。我发现很难理解其中的逻辑。

我正在阅读有关通过ardendertatmedian-of-medians的算法查找数组中第 k 个最高元素的文章。在解释复杂性的部分，作者似乎忽略了一个因素，即递归查找每个分区的成本。当然，我不能按初始枢轴对所有子阵列进行分区，对吧？那么这不会增加复杂性吗？median-of-medians

我可能正在做一些非常愚蠢的事情，但我似乎无法使这种减少工作（可能已经有一个库可以做到这一点，但这是为了自学，所以请多多包涵）。我试图通过采用中位数方法来找到整数条目数组的中位数，我在下面进行了编码：

我将此内核函数调用为：

然后我将 d_med 中的值复制到 med 中并打印出该值。不幸的是，无论输入如何，该值始终为 0。我究竟做错了什么？

编辑：我忘了提，swapGpu(a, b) 定义如下：

Edit2：如下所示，这是完整的代码。

我目前正在研究中位数 alg 的中位数。

从wiki学习后，我有一个问题：如果输入大小不能被5整除怎么办？如何使用中位数算法找到中位数？