Chr*_* A. 15 c++ algorithm stl nth-element
有没有人知道不同实现的预期运行时间和最坏情况运行时间std::nth_element？我几乎每天都使用这个算法.
我对最近的Microsoft编译器附带的STL版本特别感兴趣,但有关此主题的任何信息都很有帮助.
请注意,这不是此问题的副本.我理解存在哪些算法,但我对哪些实现使用哪种算法感兴趣.
对于背景,有众所周知的算法可以做到这一点.一个是O(n)平均情况和O(n log n)最坏情况,一个是O(n)最坏情况但实际上缓慢(中位数的中位数).还要注意,有一些有趣的实现策略可以让我们在实践中获得最快的O(n)运行时间.该标准表明,这必须是更糟糕的O(n)平均时间.
SJH*_*owe 16
预期的运行时间是O(N)大多数实现的最坏情况运行时间是O(N*N),因为大多数实现使用QuickSelect,可能是QuickSelect运行到坏分区.对于Microsoft VS2008,VS2010和VS2012来说也是如此.
现在有了新的ISO C++ 2011标准,std :: sort的复杂性已经收紧 - 它保证为O(N*log N),并且使用David Musser的IntroSort时没有更糟糕的情况: - 使用QuickSort,如果数组的某些部分遇到错误的分区,交换到heapsort.
理想情况下,应该应用std :: nth_element,但ISO C++ 2011标准并没有收紧复杂性要求.因此,在最坏的情况下,std :: nth_element可能是O(N*N).这可能是因为在David Musser的原始论文中(见这里)他没有提到如果QuickSelect变坏会应该交换什么算法.
在最坏的情况下,可以使用使用5组的中位数中位数(我已经看过一篇论文推荐的7组,但找不到它).因此,如果分区变坏,std :: nth_element的质量实现可以使用QuickSelect并交换到中位数中位数.这将保证O(N)行为.QuickSelect可以通过使用采样来改进,使最坏情况不太可能但不是不可能的.