Если вход является случайной перестановкой целых чисел от 1 до n. Среднее время выполнения (детерминированной) быстрой сортировки составляет Θ (n ^ 2). Правда о ложь?

Question

Я знаю, что наихудшее время выполнения детерминированного алгоритма быстрой сортировки (быстрая сортировка, где ось является конкретной, такой как первый элемент массива или последний элемент массива) равно Θ (n ^ 2), но является средним время выполнения дела также Θ (n ^ 2)? Я думал, что среднее время выполнения дела будет Θ (nlogn), но я не совсем уверен.

Answer 1

Такое ощущение, что это может быть домашнее задание ..

Несмотря на это, быстрая сортировка - это O (n ^ 2) наихудший случай и Θ (nlogn) средний случай.