algorithm - 在 O(n) 时间内使用黑盒算法计算中位数

Question

问题是这样的:

给定一个大小为 n 的数组 A 和算法 B 和 B(A,n)=b 其中 b 是 A 的一个元素使得 |{1<=i<=n | a_i>b}|>=n/10
|{1<=i<=n | a_i>b}|<=n/10

B的时间复杂度是O(n)。

我需要在 O(n) 中找到中位数。

我尝试通过应用 B 然后找到小于 b 的元素组来解决这个问题，让我们将这个组命名为 C。和大于 b 的元素，让我们将这个组命名为 D。我们可以通过在 O(n) 中遍历数组 A 来得到组 C 和 D。现在我可以在上面的较小组上应用算法 B，因为中值不存在并且最后应用相同的原理我可以获得中值元素。时间复杂度O(nlogn)

我似乎无法找到 O(n) 的解决方案。

这是一个家庭作业问题，我将不胜感激任何帮助或见解。

Answer 1

您应该使用函数 B() 为快速选择算法选择一个主元元素:https://en.wikipedia.org/wiki/Quickselect

看起来您已经在考虑这个过程，所以您已经有了算法，只是计算的复杂度不正确。

在每次迭代中，您在最多为前一次迭代中列表大小的 9/10 的列表上运行线性时间过程，因此最坏情况下的复杂度为

O( n + n*0.9 + n*0.9^2 + n*0.9^3 ...)

像这样的几何级数会收敛到一个常量乘数:

令 T = 1 + 0.9^1 + 0.9^2 + ...

很容易看出

T - T*0.9 = 1，所以

T*(0.1) = 1，且 T=10

因此通过所有迭代处理的元素总数小于 10n，因此您的算法需要 O(n) 时间。