Временная сложность

Сколько работы делает алгоритм

Временная сложность показывает, как растёт количество выполняемой работы при увеличении входных данных. Вместо измерения миллисекунд мы выбираем операции, которые повторяются в зависимости от размера входа, и оцениваем число таких повторений.

Простой цикл по массиву обычно даёт линейную сложность:

int sum = 0;

for (int value : numbers) {
    sum += value;
}

Если в массиве n элементов, тело цикла выполняется n раз. Поэтому временная сложность — O(n).

Смотри на то, как меняется цикл

Не каждый цикл линейный. Если управляющая переменная каждый раз уменьшается или увеличивается в несколько раз, количество итераций растёт гораздо медленнее. Например, здесь значение делится пополам до тех пор, пока не станет равно нулю:

int value = n;

while (value > 0) {
    value /= 2;
}

Чтобы увеличить количество итераций всего на одну, исходное n нужно примерно удвоить. Такой рост описывают как O(log n). Основание логарифма в Big O обычно не указывают: разные постоянные основания отличаются только постоянным множителем.

Вложенность требует внимания к диапазонам

Вложенные циклы часто означают произведение числа итераций, но оценивать нужно реальные границы каждого цикла. В следующем примере внутренний цикл проходит только по индексам после i:

for (int i = 0; i < numbers.length; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
        System.out.println(numbers[i] + numbers[j]);
    }
}

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

Вызовы методов тоже имеют стоимость

Нельзя оценивать строку только по тому, как она выглядит снаружи. Если внутри вызываемого метода есть проход по коллекции, сортировка или другая работа, её нужно включить в общую оценку. Поэтому анализ сложности всегда опирается не только на количество строк, но и на то, что реально выполняют операции.