Существует ли какая-либо формула для расчета числа проходов, которое займет алгоритм быстрой сортировки?

Question

При работе с алгоритмом быстрой сортировки я задавался вопросом, может ли быть доступна какая-либо формула или что-то вроде того, чтобы найти число проходов, которое может занять определенный набор значений для полной сортировки в порядке возрастания.

Существует ли какая-либо формула для расчета числа проходов, которое займет алгоритм быстрой сортировки?

Answer 1

Любой заданный набор значений будет иметь различное количество операций на основе метода выбора сводных значений и сортировки фактических значений.

Так что ... нет, если только аппроксимации 'между O (N log (N)) и O (N ^ 2) 'достаточно хороши.

Достаточно того, чтобы квалифицировать среднее значение по сравнению с наихудшим случаем, чтобы показать, что единственный способ определить количество операций - этона самом деле запустить быструю сортировку.