3

我们如何去除时间复杂度为 O(log n) 的集合的中位数？有什么想法？

4

9 回答 9

18

如果集合已排序，则找到中位数需要 O(1) 项检索。如果项目按任意顺序排列，则在不检查大多数项目的情况下，将无法确定中位数。如果一个人检查了大部分但不是所有的项目，这将允许一个人保证中位数将在某个范围内[如果列表包含重复项，上限和下限可能匹配]，但检查大多数列表中的项目意味着 O(n) 项检索。

如果一个集合中的信息不是完全排序的，但某些排序关系是已知的，则所需的时间可能需要 O(1) 到 O(n) 项检索之间的任何时间，具体取决于已知排序的性质关系。

于 2010-09-03T00:46:24.760 回答
5

对于未排序的列表，重复进行O(n)部分排序，直到知道位于中间位置的元素。不过，这至少是O(n)。

是否有关于正在排序的元素的任何信息？

于 2010-09-03T01:16:00.097 回答
4

试试红黑树。它应该可以很好地工作，并且通过二进制搜索你会得到你的 log(n)。它还具有 log(n) 的删除和插入时间，并且重新平衡也在 log(n) 中完成。

于 2012-06-24T22:58:59.677 回答
4

对于一般的、未排序的集合，不可能在优于 O(n) 的时间内可靠地找到中位数。您可以在 O(1) 中找到已排序集合的中位数，或者您可以在 O(n log n) 时间内自行对集合进行简单排序，然后在 O(1) 中找到中位数，给出 O(n logn n)算法。或者，最后，有更聪明的中值选择算法可以通过分区而不是排序来工作，并产生 O(n) 性能。

但是，如果该集合没有特殊属性并且您不允许任何预处理步骤，那么您将永远不会低于 O(n)，因为您需要至少检查一次所有元素以确保您的中位数是正确的。

于 2010-09-03T01:21:43.583 回答
4

这是基于 TreeSet 的 Java 解决方案：

public class SetWithMedian {
    private SortedSet<Integer> s = new TreeSet<Integer>();
    private Integer m = null;

    public boolean contains(int e) {
        return s.contains(e);
    }
    public Integer getMedian() {
        return m;
    }
    public void add(int e) {
        s.add(e);
        updateMedian();
    }
    public void remove(int e) {
        s.remove(e);
        updateMedian();
    }
    private void updateMedian() {
        if (s.size() == 0) {
            m = null;
        } else if (s.size() == 1) {
            m = s.first();
        } else {
            SortedSet<Integer> h = s.headSet(m);
            SortedSet<Integer> t = s.tailSet(m + 1);
            int x = 1 - s.size() % 2;
            if (h.size() < t.size() + x)
                m = t.first();
            else if (h.size() > t.size() + x)
                m = h.last();
        }
    }
}

删除中位数（即“s.remove(s.getMedian())”）需要 O(log n) 时间。

编辑：为了帮助理解代码，这里是类属性的不变条件：

private boolean isGood() {
    if (s.isEmpty()) {
        return m == null;
    } else {
        return s.contains(m) && s.headSet(m).size() + s.size() % 2 == s.tailSet(m).size();
    }
}

以人类可读的形式：

  • 如果集合“s”为空，则“m”必须为空。
  • 如果集合“s”不为空，那么它必须包含“m”。
  • 令 x 为严格小于“m”的元素数，令 y 为大于或等于“m”的元素数。那么，如果元素的总数是偶数，x必须等于y；否则，x+1 必须等于 y。
于 2010-09-03T02:03:44.833 回答
3

正如前面的答案中提到的，如果不触及数据结构的每个元素，就无法找到中位数。如果您要查找的算法必须按顺序执行，那么您能做的最好的事情就是 O(n)。确定性选择算法 (median-of-medians) 或 BFPRT 算法将以 O(n) 的最坏情况解决问题。您可以在这里找到更多相关信息：http ://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

但是，可以使中位数算法的中位数运行得比 O(n) 更快，使其并行。由于其分而治之的性质，该算法可以“轻松”地并行化。例如，当将输入数组分成 5 个元素时，您可能会为每个子数组启动一个线程，对其进行排序并找到该线程中的中位数。当这一步完成时，线程被连接起来，算法再次使用新形成的中位数数组运行。

请注意，这样的设计只会对非常大的数据集有益。产生线程和合并它们的额外开销使得它对于较小的集合是不可行的。这有点见识：http ://www.umiacs.umd.edu/research/EXPAR/papers/3494/node18.html

请注意，您可以在那里找到渐近更快的算法，但是它们对于日常使用来说不够实用。你最好的选择是已经提到的连续中位数算法。

于 2013-05-16T23:27:50.657 回答
2

我知道一种时间复杂度为 O(n) 的随机算法。

这是算法：

输入：由 n 个数字组成的数组 A[1...n] [不失一般性，我们可以假设 n 是偶数]

输出：排序数组中的第 n/2 个元素。

算法（ A[1..n] ，k = n/2）：

从 1...n 中随机选择一个枢轴 - p

将数组分成两部分：

L - 元素 <= A[p]

R - 元素 > A[p]

如果(n/2 == |L|) A[|L| + 1] 是中位止损

if( n/2 < |L|) 在 (L, k) 上递归

否则重新诅咒 (R, k - (|L| + 1)

复杂性：O(n) 证明都是数学的。一页长。如果你有兴趣 ping 我。

于 2010-09-05T01:52:57.953 回答
2

当然，尤达大师的随机算法与任何其他算法一样具有 n 的最小复杂度，n 的预期复杂度（不是 log n）和 n 平方的最大复杂度，如快速排序。它仍然非常好。

在实践中，“随机”枢轴选择有时可能是固定位置（不涉及 RNG），因为已知初始数组元素足够随机（例如，不同值的随机排列，或独立且同分布）或从输入值的近似或精确已知分布。

于 2011-10-11T15:18:16.493 回答
0

扩展 rwong 的答案：这是一个示例代码

// partial_sort example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (myints, myints+9);
  vector<int>::iterator it;

  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}

输出：myvector 包含：1 2 3 4 5 9 8 7 6

中间的元素将是中位数。

于 2012-06-24T22:50:44.727 回答