Основы сложности

Размер входа — отправная точка

Чтобы говорить о сложности, сначала нужно понять, что именно растёт. Обычно размер входа обозначают буквой n. Для массива это чаще всего количество элементов, для строки — количество символов, а для числовой задачи размер входа зависит от того, какие данные алгоритм действительно обрабатывает.

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

boolean containsZero = false;

for (int value : numbers) {
    if (value == 0) {
        containsZero = true;
    }
}

Если массив станет в два раза длиннее, цикл в общем случае выполнит примерно в два раза больше итераций. Такой рост называют линейным и записывают как O(n).

Почему константы обычно отбрасывают

Представим, что алгоритм два раза проходит по одному массиву:

for (int value : numbers) {
    System.out.println(value);
}

for (int value : numbers) {
    System.out.println(value * 2);
}

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

По той же причине в выражении вроде n * n + n при больших n главным становится квадратный член. Такую сложность записывают как O(n²).

Последовательно — складываем, вложенно — умножаем

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

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

Внутреннее действие выполняется для каждой пары индексов: примерно n * n раз. Отсюда оценка O(n²).