Всегда ли Quicksort имеет квадратичное время выполнения, если вы выбираете максимальный элемент в качестве точки разворота?

9

Если у вас есть алгоритм быстрой сортировки, и вы всегда выбираете самый маленький (или самый большой) элемент в качестве своей оси; Прав ли я, если предположить, что если вы предоставите уже отсортированный набор данных, вы всегда получите худшую производительность независимо от того, находится ли ваш «уже отсортированный» список в возрастающем или убывающем порядке?

Я думаю, что если вы всегда выбираете наименьший элемент для своей оси, то не имеет значения, будет ли ваш «уже отсортированный» вход отсортирован по возрастанию или по убыванию, потому что подмножество, выбранное для сортировки относительно вашей оси, всегда будет тот же размер?

algorithms time-complexity algorithm-analysis runtime-analysis sorting yoonsi
источник
2
Ваше мышление правильное, но вы также можете поспорить и посчитать время выполнения быстрой сортировки в этом случае - вы получите . O(n2)
Юваль Фильмус

Ответы:

15

Худший случай сложность для быстрой сортировки является . Это достигается путем выбора опорных точек, которые делят множество таким образом, чтобы в одной группе был только один член. При плохом алгоритме выбора поворота это может быть легко достигнуто путем выбора одного конца отсортированного набора. Ваше предположение верно.Θ(n2)

walrii
источник
2
Лучше было написать: «... Это достигается путем выбора кругов, которые делят множество так, что в одной группе только O (1) член»
@Saeed Amiri: Это верно, но лучше быть точным.
MMS
1
@SaeedAmiri: O (1) указывает, что оно пропорционально 1, что означает, что оно может быть k * 1. Реальный наихудший случай достигается, когда он равен ровно 1. Я предоставлю вам, что O (1) все еще может привести к O (n ^ 2).
Валерий
O(1)Θ(n2)Θ(n2)Θ(n2)
3

01(n−1)O(n2)

t(n)=t(n−1)+t(0)+O(n)=O(n2)
Сулава
источник