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

Question

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

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

Answer 1

Худшая сложность для QuickSort - $ theta (n^2) $. Это достигается путем выбора поворотов, которые делят набор, так что у одной группы есть только один участник. С плохим алгоритмом сбора поворота, это может быть легко достигнуто, выбрав один конец отсортированного набора. Ваше предположение верно.

Answer 2

Да! Вы думаете, что это абсолютно правильно! И, как правильно упомянуто Yuval Filmus, время работы будет $ theta (n^2) $

Answer 3

У одного Subarray будет $ 0 $ или $ 1 $ элемент, в то время как у другого будет элементы $ (n-1) $; Следовательно, это $ o (n^2) $: $$ t (n) = t (n-1)+t (0)+o (n) = o (n^2) $$