nth_element实现的复杂性 [英] nth_element implementations complexities

问题描述

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

Does anyone know both the expected running times and worst case running times for different implementations of std::nth_element? I use this algorithm nearly every day.

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

I'm specifically interested in the STL versions shipping with the recent Microsoft Compilers, but any information on this topic is helpful.

请注意，这不是该问题的重复。了解存在哪些算法，但是我对哪种实现使用哪种算法感兴趣。

Please note that this is not a duplicate of this question. I understand which algorithms exist, but I'm interested in which implementations use which algorithms.

对于背景技术，有一些著名的算法可以做到这一点。一种是O（n）平均情况，而O（n log n）最坏情况，一种是O（n）最坏情况，但实践中很慢（中位数的中位数）。
还请注意，正在谈论一些有趣的实施策略，以使最糟糕的情况-实际情况下O（n）运行时间很短。该标准说，这必须是更差的O（n）平均时间。

For background, there are well-known algorithms to do this. One is O(n) average case and O(n log n) worst case, one is O(n) worst case but slow in practice (median of medians). Also note that there is talk of interesting implementation strategies to get worst-case O(n) running times that are fast in practice. The standard says that this must be at worse O(n) average time.

推荐答案

预期的运行时间为O（N）
对于大多数实现而言，最坏的情况下运行时间是O（N * N），因为大多数实现都使用QuickSelect，并且QuickSelect可能会遇到错误的分区。
对于Microsoft VS2008，VS2010& VS2012。

The expected running time is O(N) The worst case running time for most implemententations is O(N * N) because most implementations use QuickSelect and it could be that QuickSelect runs into bad partitions. That is true for Microsoft VS2008, VS2010 & VS2012.

现在有了新的ISO C ++ 2011标准，std :: sort的复杂性已经提高了-保证为O（N * log N）并没有出现更糟的情况，因为使用了David Musser的IntroSort：-使用QuickSort，并且如果阵列的某些部分遇到不良分区，请交换到heapsort。

Now with the new ISO C++ 2011 standard, the complexity for std::sort has been tightened up - it is guaranteed to be O(N * log N) and has no worse case as David Musser's IntroSort is used: - use QuickSort and if parts of the array experience bad partitioning, swap to heapsort.

理想情况下，应该完全相同std :: nth_element，但是ISO C ++ 2011标准没有严格要求复杂性。因此，在最坏的情况下std :: nth_element可能为O（N * N）。这可能是因为在大卫·穆瑟（David Musser）的原始论文（请参见此处）中，他做了更不用说如果QuickSelect变坏了应该使用哪种算法。

Ideally exactly the same should apply std::nth_element but the ISO C++ 2011 standard has not tightened up the complexity requirements. So std::nth_element could be O(N * N) in the worst case. This could be because in David Musser's original paper (see here) he did not mention what algorithm should be swapped to if QuickSelect goes bad.

在最坏的情况下，可以使用5个一组的中位数中位数（我已经看到了一份推荐的7人小组论文，但找不到）。因此，如果分区变坏，std :: nth_element的高质量实现可以使用QuickSelect并交换到中位数。这将保证O（N）行为。通过使用采样可以改进QuickSelect，使最坏的情况不太可能发生，但并非不可能。

In the worst case, the median-of-medians using groups of 5 could be used (I have seen a paper the recommended groups of 7 but cannot find it). So a quality implementation of std::nth_element could use QuickSelect and swap to median-of-medians if partitioning goes bad. This would guarantee O(N) behaviour. QuickSelect can be improved by using sampling making the worst case unlikely but not impossible.

这篇关于nth_element实现的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！