logo标签列表

O(log n)的中位数算法

algorithmmedian
3
如何使用时间复杂度为O(log n)的方法移除一个集合的中位数？有什么想法吗？
1
这个集合在计算机中使用什么表示来存储？ - PeterAllenWebb
集合是有序的吗？如果是这样的话，它就是常数。 - Anycorn
我认为他正在寻找一种数据结构，该数据结构提供了一个O(log n)时间复杂度的中位数移除操作。 - Sheldon L. Cooper
它是否存储在平衡树上？这将产生很大的差异。 - rwong
我想做一个“结构体”，它可以在O(log n)时间内找到中位数，并在O(log n)时间内删除其他元素……你明白吗？ - Franzé Jr.
@Franzé Jr.：这正是我在答案中发布的内容。使用底层数据结构提供O(log n)的删除功能，例如自平衡二叉搜索树，您可以跟踪中位数并以O(1)的时间提供它，并在O(log n)时间内删除元素。 - Sheldon L. Cooper
9个回答
18
如果集合已排序，则查找中位数需要O(1)次项目检索。如果项目在任意顺序中，未经检查大部分项目将无法确定中位数。如果已检查了大多数但不是全部项目，则可以确保中位数在某个范围内[如果列表包含重复项，则上限和下限可能匹配]，但是检查列表中大多数项目意味着需要进行O(n)个项目检索。
如果在一个不完全有序但某些排序关系已知的集合中具有信息，则所需时间可能需要O(1)到O(n)之间的任何位置的项目检索，具体取决于已知排序关系的性质。
5
但是插入操作本身并不是自由的；它们最多是O(1)，而且有n个...所以会增加一个O(n)的因子。 - Tyler McHenry
1
@Tylle McHenry 虽然你所说的是正确的，但可能在插入时承担成本比在删除时更容易。 - aaronasterling
1
@aaronsterling -- 这并不改变算法必须是O(n)的事实。无论你是在插入时还是在删除时付出代价，你都必须接触每个项目。 - Michael Dorfman
Nico的解决方案表明，如果我们假设集合被存储为数组，则O(n)最小值是正确的，但是另一种替代数据结构可以允许O(logn)中位数查找时间。 - Simon Woodside
@sbwoodside: 如果数据项之间没有已知的排序关系，则查找中位数将需要O(n)时间。在红黑树中查找存储的数据的中位数更快，因为其中的数据具有已知的排序关系。当然，即使一个集合没有被“完全”排序，它也可能具有一些可以帮助查找中位数的排序关系，但是对于没有已知排序关系的数据，我的观点仍然成立。 - supercat
显示剩余3条评论
5
对于未排序的列表，需要反复进行 O(n) 部分排序 直到找到位于中间位置的元素。这至少需要 O(n) 的时间复杂度。请问这些元素是否有任何排序信息？
部分排序是O(kn)，其中k是所需元素的排名。对于中位数元素，我们希望k = n/2。因此，该算法的时间复杂度为O(n^2)。 - alandplm
1
我应该删除我的回答。（自从我发布它以来已经过去了十年。）我的观点是，只要N个元素的列表从未被“处理”（解析、排序、转换为数据结构），时间至少为N（每个元素必须至少访问一次），因此寻找O(log N)的问题直到问题被编辑以澄清假设（特别是在数据结构或预处理的选择上）才能有答案。该问题也可以通过具体询问应使用哪些数据结构等来澄清。 - rwong
还有一个问题是“从数据摄取（N个项目）到第一次查询（和项目删除）的时间”以及“到后续查询（和项目删除）的时间”。例如，如果选择数据摄取是完全排序并将它们放在平面数组上（时间O（N log N）最佳和平均值；空间O（N）；中位数枢轴可以帮助避免最坏情况，归并排序可以保证最佳时间，但需要双倍的空间要求），则后续操作的时间始终为O（1）。 - rwong
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”必须为null。
  • 如果集合“s”不为空，则它必须包含“m”。
  • 令x是严格小于“m”的元素数，y是大于或等于“m”的元素数。然后，如果元素总数是偶数，则x必须等于y；否则，x + 1必须等于y。
4
对于一般的未排序集合，要可靠地在O(n)时间内找到中位数是不可能的。你可以在O(1)时间内找到已排序集合的中位数，或者你可以轻松地在O(n log n)时间内对集合进行排序，然后在O(1)时间内找到中位数，从而得到一个O(n logn n)算法。或者，最后，还有更聪明的中位数选择算法，可以通过分区而不是排序来工作，并产生O(n)性能。
但是，如果集合没有特殊属性并且不允许任何预处理步骤，您将永远无法低于O(n)，因为简单的事实是您需要至少检查所有元素一次以确保您的中位数是正确的。
4
尝试使用红黑树。它应该能够很好地工作，并且通过二分查找可以得到log(n)的时间复杂度。它的插入和删除时间也是log(n)，再平衡也是log(n)。
这是一个很好的答案，因为它表明其他回答者假设集合存储在简单数组中。 - Simon Woodside
我们是否假设实际创建集合的O(n*log(n))复杂度不被考虑？ - Eduardo
3
如之前所述，没有办法在不触及数据结构的每个元素的情况下找到中位数。如果您要查找的算法必须依次执行，则最好的方法是O(n)。确定性选择算法（中位数算法）或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 请注意，您可以在那里找到渐近更快的算法，但是它们对于日常使用来说不太实用。您最好的选择是先前提到的顺序中位数算法。
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]是中位数，停止

如果(n/2 < |L|)，则对(L，k)进行递归

否则，对(R，k - (|L| + 1))进行递归

复杂度：O(n)

证明是全数学的。一页长。如果您感兴趣，请与我联系。

不，这是O(n)的时间复杂度，将数组分成L和R需要线性时间。 - sdcvvc
2

尤达大师的随机算法，像其他任何算法一样，最小复杂度为n，期望复杂度为n（不是log n），最大复杂度为n平方，就像快速排序一样。它仍然非常好。

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

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

中间的元素将是中位数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接