Сложности реализации nth_element

Question

Кто-нибудь знает как ожидаемое время работы, так и наихудшее время работы для разных реализаций std::nth_element? Я использую этот алгоритм почти каждый день.

Меня особенно интересуют версии STL, поставляемые с недавними компиляторами Microsoft, но любая информация по этой теме полезна.

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) и не имеет худшего случая, поскольку используется IntroSort Дэвида Муссера: используйте QuickSort, и если части массива испытывают плохое разделение, замените его на heapsort.

В идеале то же самое должно применяться std :: nth_element, но стандарт ISO C++ 2011 не затягивает требования сложности. Таким образом, std :: nth_element может быть O (N * N) в худшем случае. Это может быть связано с тем, что в оригинальной работе Дэвида Муссера (см. here) он не упомянул, какой алгоритм должен быть заменен, если QuickSelect плохо работает.

В худшем случае можно использовать медианы медианов, использующих группы по 5 (я видел документ, рекомендованный группой из 7, но не могу найти его). Таким образом, качественная реализация std :: nth_element может использовать QuickSelect и обмениваться с медианными медианами, если разбиение на разделы плохое. Это гарантировало бы поведение O (N). QuickSelect можно улучшить, используя выборку, что делает наихудший случай маловероятным, но не невозможным.

Answer 2

cppreference говорит, сначала сортирует, а затем находит п-й элемент, но этим способ в среднем должна быть O(n log n) (по сравнению на основе алгоритмов сортировки), но они писали средний O (п), представляется неправильным, за исключением использования сортировки, как радикс sort, ... но поскольку у него есть общий ввод на основе сравнения, кажется, что невозможно использовать сортировку radix или любой другой вид, который не основан на сравнении. во всяком случае, использование быстрых алгоритмов сортировки лучше, чем использование обычного алгоритма выбора на практике (как памяти, так и среднего времени).

Answer 3

Реализация в GCC 4.7 использует introspective selection Дэвида Муссера (здесь у вас есть его paper с подробным описанием интросорта и introselect). Согласно этим документам, наихудшим временем выполнения является O (n).