Может ли sort () в C ++ иметь производительность n ^ 2? - PullRequest
Новая
       3

Может ли sort () в C ++ иметь производительность n ^ 2?

4 голосов
/ 03 июня 2011

При попытке оценить производительность программы я всегда рассматривал функцию sort () как функцию с наихудшей производительностью-n ^ 2.Однако я натолкнулся на страницу Википедии:

sort (C ++)

В которой говорится, что sort () библиотеки GNU C использует сначала гибридный алгоритм сортировки, называемый Introsort,затем сделайте вставку сортировки.Соответствующая страница Introsort утверждает, что этот алгоритм имеет худшую производительность nlogn.Однако, поскольку я не знаком с этим алгоритмом, у меня все еще есть следующие опасения по поводу sort ():

1) Может ли гибридный алгоритм, используемый GNU sort (), гарантировать производительность O (nlogn)?Если да, то насколько большими могут быть постоянные издержки nlogn?

2) Существуют ли другие реализации, которые могут привести к тому, что sort () будет работать хуже, чем эта (или лучше, что было бы здорово)?

РЕДАКТИРОВАТЬ: Ответ Кевину: упомянутая сортировка () является std :: sort ().

Спасибо!

Ответы [ 5 ]

5 голосов
/ 03 июня 2011

Использование быстрой сортировки и внутренней сортировки (которая является вариантом первой, с гарантированной O(n log n) производительностью, достигаемой переключением на heapsort на входах для наихудшего случая) вместо других теоретически лучших алгоритмов, таких как mergesort, связано с тем,Средний регистр такой же, а константы значительно ниже (в константы можно включить тот факт, что его можно отсортировать на месте, поэтому перераспределений нет, и копий).И наихудший случай - это плохо, но совершенно невозможно.В целом предполагается, что производительность sort составляет O( n log n ).

Если вас беспокоят скрытые константы, тогда вопрос не теоретический, а скорее вопрос производительности.Когда вы пытаетесь оптимизировать, вам лучше измерить алгоритм на ваших реальных данных, проанализировать результаты измерения, а затем определить, где потрачено время и можно ли его улучшить.Но это проблема, совершенно отличная от теоретической.

3 голосов
/ 03 июня 2011

Если ваша стандартная библиотека не дает никаких гарантий, кроме ISO 14882, то, похоже, нет формальной границы для поведения наихудшего случая sort() - указана только средняя сложность.В стандарте есть сноска, в которой упоминается, что вы должны использовать stable_sort() или partial_sort() вместо sort(), если вам небезразлично:

http://www.kuzbass.ru:8086/docs/isocpp/lib-algorithms.html#lib.alg.sorting

25.3.1.1 - сортировка[lib.sort] 

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last)

template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)

  1. Эффекты: сортирует элементы в диапазоне [первый, последний).

  2. Сложность: Приблизительно N log N (где N == последний - первый) сравнений в среднем. *

[Сноска. Если важно поведение в худшем случае stable_sort () (lib.stable.sort) или part_sort () (lib.partial.sort) должны быть использованы.--- end footnote]

Определенные реализации библиотеки, вероятно, дают более строгие гарантии, чем стандартные.И, конечно, полезно взглянуть на код напрямую.Опять же, это зависит от того, насколько портативным вы хотите, чтобы это было.

2 голосов
/ 03 июня 2011

Интросорт имеет фактически O (n log (n)) наихудшее время выполнения, а не O (n ^ 2). Также см. это замечание в спецификации SGI STL:

Более ранние версии сортировки использовали алгоритм быстрой сортировки, используя пивот выбирается по медиане из трех. Quicksort имеет O (N log (N)) средней сложности, но квадратичная сложность наихудшего случая. Однако текущая реализация сортировки использует интросорт алгоритм чей сложность наихудшего случая O (N log (N)) . Introsort очень похож на средний из трех быстрой сортировки, и находится в в среднем менее быстр, чем быстрая сортировка.

1 голос
/ 03 июня 2011

Да, это вариация быстрой сортировки, использующая динамическую сортировку для подозрительного ввода патологической быстрой сортировки. Он смотрит на глубину рекурсии, а когда он падает слишком глубоко, он сортирует с помощью heapsort, удаляя любое патологическое поведение. Это гарантирует N log N. Постоянные издержки N log N (qsort vs heapsort) не о чем беспокоиться.

Сортировка вставок используется, когда элементов очень мало (около 16).

0 голосов
/ 03 июня 2011

http://en.wikipedia.org/wiki/Sorting_algorithm перечисляет несколько алгоритмов сортировки с n ^ 2 производительностью. У него есть один с п! спектакль. В нем также перечислены несколько несопоставимых сортов, производительность которых зависит от других факторов.

...