Основные классы сложности

Постоянная и логарифмическая сложность

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

int first = numbers[0];

При O(log n) количество шагов растёт очень медленно: на каждом шаге рассматриваемая часть задачи обычно уменьшается в несколько раз. Если вход удвоился, число шагов увеличивается примерно на константу.

Линейный и линейно-логарифмический рост

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

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

O(n log n) растёт быстрее линейной сложности, но существенно медленнее квадратной. Такой класс часто встречается у эффективных алгоритмов сортировки и у решений, которые выполняют логарифмическую работу для многих элементов. Важно узнавать сам характер роста, даже если конкретный алгоритм будет изучаться позже.

Квадратный рост

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

for (int left : numbers) {
    for (int right : numbers) {
        System.out.println(left + right);
    }
}

При удвоении n число пар увеличивается примерно в четыре раза. Поэтому разница между O(n) и O(n²) становится особенно заметной на больших входах.

Быстро растущие классы

Существуют алгоритмы с ростом O(2ⁿ), O(n!) и ещё быстрее. Они возникают, когда решение порождает множество комбинаций или вариантов, и даже небольшое увеличение входа резко увеличивает объём работы. На маленьких n такой алгоритм ещё может быть практичным, но масштабируется он намного хуже полиномиальных вариантов.

Полезный порядок для сравнения типичных классов выглядит так: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!). Это не список «хороших» и «плохих» алгоритмов, а шкала того, насколько быстро растут затраты.