Какова временная сложность std :: sort () в стандартной библиотеке C ++? - PullRequest
Новая
       11

Какова временная сложность std :: sort () в стандартной библиотеке C ++?

34 голосов
/ 19 декабря 2010

Какова сложность std::sort() в стандартной библиотеке C ++?Какой сорт применяется?Есть ли там какое-либо правило применения какого-либо конкретного алгоритма сортировки?

Ответы [ 6 ]

27 голосов
/ 19 декабря 2010

std::sort должен иметь среднеарифметическую линейную (n log n) сложность времени. Любой алгоритм может использоваться при условии соблюдения этого требования к сложности времени. Нет наихудшего требования к временной сложности.

Если вам нужна функция гарантированной сложности времени наихудшего случая, используйте std::stable_sort, которая имеет квазилинейную сложность времени наихудшего случая (n log ^ 2 n).

5 голосов
/ 30 июня 2014

Стандарт гарантирует

Из стандарта C ++ 11/14, std::sort гарантированно будет иметь:

§25.4.1.1 / 3

Сложность: O(N log(N)) (где N == last - first) сравнения.

Другой, стабильный, стандартный алгоритм сортировки (а именно std::stable_sort) гарантированно будет иметь:

25.4.1.2 / 3

Сложность: выполняется не более N log2(N) (где N == last - first) сравнений;если доступно достаточно дополнительной памяти, это N log(N).

Для std::forward_list::stable, вместо:

23.3.4.6 / 26

Сложность: приблизительно N log(N) сравнений, где N равно distance(begin(), end()).

То же самое относится к std::list:

23.3.5.5 / 31

Сложность: приблизительно N log(N) сравнения, где N == size().

Алгоритм сортировки

Стандарт C ++ не поддерживаетукажите, какой алгоритм сортировки применять в любом из вышеперечисленных случаев.Это было бы часто и ненужным ограничением реализации.

Если вам нужно знать, вам может повезти, если вы посмотрите на конкретную спецификацию компилятора.Например, для GNU GCC вы должны начать с здесь .

5 голосов
/ 19 декабря 2010

Сложность O(n log n). Насколько я знаю, некоторые распространенные реализации используют introsort:

http://en.wikipedia.org/wiki/Introsort

5 голосов
/ 19 декабря 2010

http://en.wikipedia.org/wiki/Sort_(C%2B%2B)

Конкретный алгоритм сортировки не является обязательным и может варьироваться в зависимости от реализации. Например, библиотека GNU Standard C ++ использует гибридный алгоритм сортировки: сначала выполняется интросортировка до максимальной глубины, равной 2 × log2 n, где n - количество элементов, за которым следует сортировка вставкой по результату. [1 ] Безотносительно реализации, сложность должна быть O (n log n) сравнений в среднем. [2]

1 голос
/ 19 декабря 2010

Если вы имеете в виду std::sort():

Это из стандарта C ++ 03, раздел 25.3. Гарантия исполнения: 

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 == последний - первый) сравнений в среднем.

0 голосов
/ 17 июля 2018

Стандарт C ++ указывает , что время выполнения в худшем случае из std::sort() находится в O(n log n) - где n - количество отсортированных элементов (ср. C ++ 11, раздел 25.4.1.1).

Стандарт не определяет конкретный алгоритм сортировки.

Таким образом, соответствующая реализация std::sort() может свободно выбирать любой алгоритм, который удовлетворяет вышеуказанному требованию времени выполнения.

Обратите внимание, что стандартные версии C ++ до C ++ 11 просто требовали, чтобы среднее время выполнения из std::sort() находилось в O(n log n).

См. Также вопрос stackoverflow Какие алгоритмы используются в C ++ 11 std :: sort в различных реализациях STL? , чтобы понять, какие именно алгоритмы сортировки используются в реальных реализациях STL.

...