c++ - nth_element 实现复杂性

Question

有人知道 std::nth_element 的不同实现的预期运行时间和最坏情况下的运行时间吗？我几乎每天都使用这个算法。

我对最近的 Microsoft 编译器附带的 STL 版本特别感兴趣，但有关此主题的任何信息都会有所帮助。

Please note that this is not a duplicate of this question.我了解存在哪些算法，但我对哪些实现使用哪些算法感兴趣。

作为背景，有众所周知的算法可以做到这一点。一种是 O(n) 平均情况和 O(n log n) 最坏情况，一种是 O(n) 最坏情况但在实践中很慢(中位数的中位数)。另请注意 there is talk of interesting implementation strategies to get worst-case O(n) running times that are fast in practice .标准说这必须是更糟糕的 O(n) 平均时间。

Answer 1

预计运行时间为 O(N)大多数实现的最坏情况运行时间是 O(N * N)，因为大多数实现都使用 QuickSelect，并且可能是 QuickSelect 运行到错误的分区中。Microsoft VS2008、VS2010 和 VS2012 也是如此。

现在有了新的 ISO C++ 2011 标准，std::sort 的复杂性得到了加强 - 它保证为 O(N * log N) 并且没有更糟的情况，因为使用了 David Musser 的 IntroSort: - 使用快速排序，如果部分数组遇到错误分区，则交换到堆排序。

理想情况下，std::nth_element 应该完全相同，但 ISO C++ 2011 标准并未收紧复杂性要求。所以 std::nth_element 在最坏的情况下可能是 O(N * N) 。这可能是因为在 David Musser 的原始论文(参见 here)中，他没有提到如果 QuickSelect 出错应该换成什么算法。

在最坏的情况下，可以使用使用 5 组的中位数中位数(我看过一篇论文推荐的 7 组但找不到)。因此，如果分区出错，std::nth_element 的高质量实现可以使用 QuickSelect 并交换到中位数。这将保证 O(N) 行为。 QuickSelect 可以通过使用抽样来改进，使最坏的情况不太可能发生但并非不可能。