问题标签 [median-of-medians]

为了避免快速选择的 O(n^2) 最坏情况，我知道 2 个选项：

1. 随机选择一个枢轴索引

2. 使用中位数的中位数 (MoM) 选择一个近似中位数并以此为中心

当使用快速选择的 MoM 时，我们可以保证最坏情况 O(n)。当使用(1)时，我们不能保证最坏情况O(n)，但是算法到O(n^2)的概率应该是极小的。(2) 的开销成本远高于 (1)，后者几乎不会增加额外的复杂性。

那么我们什么时候应该使用其中一个呢？

假设 A = [1, 2, 3, 4, 5, 6, 7, 8, 9]。我必须在这里找到中位数，即 5，并且我需要使用快速选择和中位数的概念。我制作了以下代码，但由于某种原因，它输出 4 这是错误的。我哪里错了？

以下只是后面功能需要的一些辅助功能。

对于以下内容，我编写了中位数的代码。这样做是将整个数组划分为 5 个元素的组，最多 1 个包含少于 5 个元素的组。

现在这是它使用中位数中位数中的中位数对数组进行分区的部分

这是 quick_select 的功能

这是 main() 的函数

我正在尝试在 Java 中实现中位数算法的中位数。该算法应确定一组数字的中位数。我试图在维基百科上实现伪代码：

https://en.wikipedia.org/wiki/Median_of_medians

我遇到缓冲区溢出，不知道为什么。由于递归，我很难跟踪代码。

确认 n（在伪代码中）或 i（在我的代码中）代表中位数的位置？所以让我们假设我们的数组是 number = {9,8,7,6,5,4,3,2,1,0}。我会调用 select{numbers, 0, 9,4)，对吗？

我不明白中间值的计算？为什么要除以 10？也许伪代码有错误？

谢谢你的帮助。

我正在尝试实现中位数算法/ BFPRT 算法的中位数。

main 中数组的检查输出是 5，但是我的代码甚至没有达到正确的输出（输出 -1，因为它没有达到 i>k 或 i<k 条件中的必要条件）。

任何帮助将不胜感激。

我越是绕开它，我的代码就越混乱。请原谅凌乱的代码：

我被要求为大小为 g 的组找到中位数算法的一般形式的运行时间。从、 和的常见示例g=3,5,7中T(n)=T(n/5)+T(2n/3)+cn，奇数的一般情况似乎是。T(n)=T(n/5)+T(7n/10)+cnT(n)=T(n/7)+T(5n/7)+cnT(n)=T(n/g)+T(1-(n/(2g)*(g+1)/2))+cn

但是，我正在努力使用什么作为偶数 g 的中位数，其中中位数将存在于两个元素之间，而不是实际存在于集合本身中。有人告诉我，我可以忽略地板和天花板。直觉告诉我它应该只是T(n)=T(n/g)+T(1-(n/(2g)*(g)/2))+cn，但我不禁觉得我错过了一些东西。

任何人都可以就算法如何处理偶数组提供建议吗？我想一旦我理解了算法，我应该能够找到运行时间。