Big O

Асимптотика описывает, как растут затраты алгоритма при увеличении размера входа n. Она не измеряет секунды и не учитывает постоянные множители, но позволяет сравнить масштабируемость решений.

Обозначения

Запись	Смысл
O(g(n))	верхняя асимптотическая граница
Ω(g(n))	нижняя асимптотическая граница
Θ(g(n))	точная граница одного порядка роста

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

Частые порядки роста

Сложность	Пример
O(1)	доступ к элементу массива по индексу
O(log n)	поиск в сбалансированном дереве
O(n)	один полный проход
O(n log n)	эффективная сортировка сравнением
O(n²)	сравнение каждой пары
O(2ⁿ)	перебор всех подмножеств

Правила упрощения:

• 3n + 20 превращается в O(n);
• n² + n превращается в O(n²);
• два последовательных прохода дают O(n + n) = O(n);
• вложенные независимые проходы по n дают O(n²);
• для разных входов точнее писать O(n * m), а не O(n²).

for (int value : values) {        // n
    if (value == target) return true;
}
return false;                      // время O(n), память O(1)

Амортизированная сложность

Одна операция расширения ArrayList стоит O(n), но происходит редко. Последовательность многих добавлений распределяет эту цену, поэтому add в конец имеет амортизированную стоимость O(1).

Для рекурсии оценивают и время, и глубину стека. Например, линейный рекурсивный обход может иметь время O(n) и дополнительную память O(n). См. Рекурсия.

Вопросы для собеседования

1. Что отбрасывает Big O? Константы и слагаемые меньшего порядка.
2. Всегда ли O(1) быстрее O(n)? Нет на любом конкретном малом входе; асимптотика описывает рост.
3. Чем O отличается от Θ? O даёт верхнюю границу, Θ — верхнюю и нижнюю одного порядка.
4. Почему два вложенных цикла не всегда O(n²)? Границы могут зависеть от разных размеров или суммарно выполнять только n шагов.
5. Что значит амортизированное O(1)? Средняя цена операции в длинной последовательности, включая редкие дорогие шаги.
6. Как оценить память? Посчитать дополнительное хранилище относительно входа, включая стек вызовов.