Что такое сложность времени для быстрой сортировки на месте?

Question

Я знаю, что сложность пространства уменьшается с O (n) до O (log n). Но как насчет сложности времени? Требуется ли столько же времени для выполнения обычной версии быстрой сортировки?

Answer 1

Существуют реализации QuickSort, которые работают на O (nlogn) наихудшем случае, и что касается вашего вопроса, нет лучшей, чем O (nlogn) сортировки на основе наихудшего сравнения, и поскольку быстрая сортировка равна 1, доказано, что O (nlogn) не может быть побежден в любом случае.

единственная реализация QuickSort, которую я знаю, на месте, но в любом случае все, что вы можете улучшить, это константы быстрой сортировки, кроме того, что вы упомянули, требуемое пространство можно уменьшить до O (1) (итерационная версия) и O (logn) в рекурсивной версии.

Answer 2

Quicksort - это алгоритм рекурсивной сортировки по месту, что вы имеете в виду под этим вопросом? Не существует некомпактной версии быстрой сортировки. Поскольку это рекурсивный алгоритм «разделяй и властвуй», легко показать, что, как вы говорите, сложность пространства равна по крайней мере O (log n). Как было отмечено, если вы используете итеративную реализацию, может быть меньше, полнота пространства будет O (1).

Сложность алгоритма усредняется O (n log n), является O (n * n) наихудшим случаем в реализации по умолчанию. Худший случай, когда список уже отсортирован.

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