nth_element实现的复杂性(nth_element implementations comp

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

我在STL版本，以与微软最近出货的编译器特别感兴趣，但是关于这个主题的信息是有帮助的。

请注意，这不是这个问题的一个副本。 我明白哪些算法存在，但我感兴趣的是其实现使用哪些算法。

对于背景，有著名的算法来做到这一点。 一个是O（n）的平均情况，并为O（n log n）的最坏的情况下，一个是O（n），最坏的情况，但在实践中慢（中位数的中位数）。 另外请注意， 有一种有趣的实施策略的谈话得到最坏情况下O（n）的运行时间是在实践中快速 。 该标准说，这必须是在糟糕的O（n）的平均时间。

Answer 1:

预计运行时间为O（N）运行时间对于大多数implemententations最坏的情况是O（N * N），因为大多数实现使用QuickSelect，它可能是QuickSelect运行到坏的分区。 对于微软VS2008，VS2010和VS2012是真的。

现在，随着新的ISO C ++ 2011标准中，对于性病的复杂::排序已经收紧了 - 这是保证O（N *日志N），并没有更糟糕的情况下，大卫·马瑟的内省排序时： - 使用快速排序，如果该阵列体验不好分割的部分，交换到堆排序。

理想的情况是完全一样的应适用的std :: nth_element但ISO C ++ 2011标准还没有收紧的复杂性要求。 因此，性病:: nth_element可能是O（N * N），在最坏的情况。 这可能是因为在大卫马瑟的原始文件（见这里 ），他没有提到什么算法应该交换到如果QuickSelect变坏。

在最坏的情况下，使用5可以使用组中位数的中位数（我已经看到了纸的7推荐的组，但不能找到它）。 所以，如果分区变坏质量实现的std :: nth_element都可以使用QuickSelect和交换，以中位数的中位数。 这将保证O（N）行为。 QuickSelect可以通过取样使最坏的情况并非完全没有可能得到改善。

Answer 2:

在GCC 4.7实现使用内省选择由大卫·马瑟（在这里你有他的论文给予的内省排序和introselect细节）。 根据这些文件，在最坏情况下的执行时间为O（n）。

Answer 3:

cppreference说，首先排序，然后查找第n个元素，而是通过这种方式平均值应O(n log n) （通过比较基于排序算法），但他们写道平均为O（n），似乎不正确，除了使用排序似基数排序，......但由于它具有通用的比较基础投入，似乎是不可能的使用基数排序或任何其他类型的不基于比较。 无论如何，采用快速排序算法比在实践中（存储器和平均时间），使用正常选择算法更好。

文章来源: nth_element implementations complexities