问题标签 [median-of-medians]

你好，我这学期正在学习算法课程的介绍。但是我在计算中位数算法中位数的时间复杂度时遇到了一些问题（here）。我想知道如何获得T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn..

我认为我不能将 mater theorem 应用于上面的表达式，维基百科说我应该使用归纳，但我不知道如何..

我知道中位数算法的中位数公式是： T(n)<= T(0.7n)+T(0.2n)+O(n)并且O(n)来自于找到每个块的中位数（大小为 5），我想知道为什么需要 O(n) 才能找到每个块的中位数.. 听起来像找到一个块的中位数需要O(1). 这怎么可能？

我在 java 中有一个快速排序代码，我想改进它。改进后的代码应该比快速排序代码花费更少的时间。但是，当使用我改进的实现 3 分区中位数的代码时，需要多花 400 毫秒。有人可以帮我解决这个问题吗？如果可能的话，你能建议我其他可能的方法来改进我的代码吗？我有 10,000 到 1000 万个整数要排序。

快速排序

改进的代码

在过去的几天里，我一直在努力编写这个算法，但没有成功。该代码有效，并且大多数时候它给了我正确的结果，但在某些情况下它会失败。例如对于这个数组 {3, 8, 1, 9, 10, 7, 6, 2, 5, 4} 和 k = 6，它应该给我 6 作为结果，但它给我 7。有人可以帮助我吗？我不知道有什么问题。

这是代码：

在此先感谢大家

（注意：在我的示例中，我将数组划分为包含 5 个元素的子数组）

我知道中位数算法将 n 输入数组拆分为 floor(n/5) 个组，其中包含一个额外的包含 (n)mod5 元素的组，然后找到每个排序组的中值元素（第 3 个元素在具有 5 个元素的组）等等。

我的问题是如果其中一个组有 2 个或 4 个元素，哪个元素将被选为该组的中位数（假设该组已经排序）。

解释第一个算法的图像

大小为 a 的子列表的广义中位数

从这个算法中，我们可以看到，为了获得算法的线性运行时间，常数必须大于 4。但是，我想知道如果我划分为 n/8 个子列表并选择第 4 个最大的数会发生什么每个子列表作为中位数。

我希望运行时间是线性的，因为 8 > 4 但是当我计算运行时间时，我发现 O(nlogn)。 计算大小为 8 的子列表

有人可以告诉我我做错了什么，并向我解释为什么子列表的大小应该总是奇数吗？

我的 Java 代码有问题...我已经盯着它看了 10 多个小时，但我只是找不到我犯的错误。

我的任务是通过将数组拆分为最大长度为 5 的数组并查找它们的中位数来实现“中位数的中位数”算法。然后你查找这些中位数的中位数并将你的主数组分成两部分，一个具有较小的值，另一个具有较大的值。通过这些数组的长度，您现在可以决定必须在哪个数组中查找哪个位置，然后重复算法，或者如果两个数组的大小相同，则完成。

但不知何故，在大多数情况下，我的算法与正确结果相差一两个位置。所以我认为，某处有一个小错误，可能只是循环的范围或类似的东西。因此，例如，我测试了数组{0,1,2,3,4,5,6,7,8}，因此中位数为 4，但我的程序以3结果作为响应。

我绝对知道，这是一大堆代码，我的问题可能不完全是 StackOverflow 的用途。同样在大多数情况下，我不喜欢让其他人查看我的代码，但我很绝望，因为我无法以某种方式找到我犯的错误。因此，如果你们中的某个人能够从中立的位置查看它，并可能给我一个小提示，为什么它没有按应有的方式工作，我将非常感激。

非常感谢

假设一个shape和 typenumpy数组。需要通过元素方式的均值中值计算的行。具体来说，行索引被划分为“桶”，每个桶都包含这样的索引。接下来，在每个桶中，我计算平均值，并在得到的平均值中进行最终的中值计算。Xm x nfloat64Xmbm/b

澄清它的一个例子是

如果b除法，该程序可以正常工作，m因为np.array_split()导致将索引分成相等的部分并且数组buckets是二维数组。

b但是，如果不除，它就不起作用m。在这种情况下，np.array_split()仍会拆分为b桶，但大小不等，这对我的目的来说很好。例如，如果b = 3它将索引 {0,1,...,9} 拆分为 [0 1 2 3]、[4 5 6] 和 [7 8 9]。这些数组不能相互堆叠，因此该数组buckets不是二维数组，不能用于索引X_bucketed。

我怎样才能使这项工作适用于大小不等的桶，即让程序计算每个桶内的平均值（不管它的大小），然后计算桶的中位数？

我无法完全掌握蒙面数组，我不确定是否可以在这里使用。

对于一个项目，我想比较不同中值查找算法的运行时间。我从“Medians of Medians”开始，基本上使用了Geeks for Geeks找到的代码。

我通过与计算中位数的标准 python 方法进行比较来测试它。

由于未知的原因，我的运行时间太高而且是错误的。在大约 10 个 Mio 元素的数组中查找中位数需要以下时间：

我在 Geek for Geeks 上找到的实现有问题吗？应该反过来。标准 Python 方法的运行时为O(n log n)，Median of Medians 运行在 中O(n)，所以它应该更快！

有谁知道我做错了什么并且可以给我一个提示如何解决它？

在 Google 上的几篇文章（例如https://cs.stackexchange.com/questions/125995/median-of-medians-proof-for-time-complexity）和文章中，我看到了以下时间复杂度重现中位数的中位数：

T(n) <= T(n/5) + T(7n / 10) + O(n)

但我很困惑，因为这种递归似乎将 MoM 视为嵌入到快速选择中，因此是快速选择的递归公式，用于在使用 MoM 找到近似枢轴时找到精确的中位数。

如果我们只是想使用 MoM 找到一个近似中位数，那么递归是多少？会不会只是

T(n) <= T(n/5) + O(n) ?