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