Quelle est la complexité temporelle de l'algorithme de tri rapide?

Временная сложность алгоритма быстрой сортировки:

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