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

Чтобы определить временную сложность, нужно:

Проанализировать, сколько раз выполняются основные операции (например, сравнения и перестановки элементов) в худшем, среднем и лучшем случаях.
Выразить это количество операций через функцию от n.

Например, для сортировки пузырьком во вложенных циклах сравниваются пары элементов, что даёт примерно n² операций, значит временная сложность — O(n²).

Пример: сортировка массива с помощью сортировки пузырьком и оценка сложности:

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Здесь два вложенных цикла по n, значит временная сложность — O(n²).

Для более эффективных алгоритмов, например, быстрой сортировки, временная сложность в среднем — O(n log n).

Как определить временную сложность алгоритма сортировки массива?