Jak určit časovou složitost algoritmu rychlého třídění?

Временная сложность алгоритма быстрой сортировки (QuickSort) зависит от выбора опорного элемента (pivot) и распределения данных.

• В среднем и лучшем случае сложность — O(n log n), где n — количество элементов. Это происходит, когда массив делится примерно пополам на каждом шаге.
• В худшем случае (например, когда массив уже отсортирован и выбирается крайний элемент как pivot) сложность становится O(n²).

Для оценки временной сложности анализируют количество сравнений и перестановок на каждом уровне рекурсии и суммируют по всем уровням.

Пример вызова быстрой сортировки на Java:

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Здесь partition — функция, которая выбирает pivot и разделяет массив.