Big O

Big O (O-нотация) — это математический символ, которым в IT обозначают верхнюю границу сложности алгоритма: сколько времени он выполняет задачу или сколько памяти съедает при росте объёма данных $n$.

Что даёт

Big O показывает не секунды или мегабайты (которые зависят от мощности сервера), а динамику. Она помогает понять, как повладеет себя код, если в базу прилетит не 100 записей, а 10 миллионов.

Основные классы сложности по возрастанию аппетитов:

• $O(1)$ — константная. Время выполнения не зависит от $n$. Выборка элемента из хэш-таблицы по ключу или взятие элемента из массива по индексу.
• $O(\log n)$ — логарифмическая. С каждым шагом объем работы делится на константу. Бинарный поиск по отсортированному массиву или поиск по B-tree индексу в PostgreSQL.
• $O(n)$ — линейная. Время растёт пропорционально объёму данных. Обычный перебор массива (for loop) или Full Scan таблицы в MySQL.
• $O(n \log n)$ — линейно-логарифмическая. Классическая сложность быстрых сортировок (QuickSort, MergeSort).
• $O(n^2)$ — квадратичная. Вложенные циклы по одному и тому же массиву. Сюда легко просесть при неаккуратных JOIN без индексов.
• $O(2^n)$ — экспоненциальная. Рекурсивный расчёт чисел Фибоначчи «в лоб». На продакшене это гарантированный пародийный вызов OOM Killer или зависание процесса.

Как использовать

Оценку по Big O применяют при проектировании архитектуры, написании запросов и прохождении секций по алгоритмам.

1. Оптимизация баз данных. Если выборка из таблицы на 500 000 строк занимает секунды, смотрим EXPLAIN. Отсутствие индекса превращает поиск из $O(\log n)$ в $O(n)$. Добавление индексов сводит время отклика к миллисекундам.
2. Выбор структур данных. Если в коде нужно часто проверять наличие элемента в коллекции, обычный список/массив ($O(n)$) меняют на Set или HashMap ($O(1)$).
3. Баланс Time vs Space. Часто временную сложность $O(n^2)$ удаётся сбить до $O(n)$, но ценой выделения дополнительной памяти ($O(n)$ по Time/Space Complexity) через кэширование или хэш-маппинг.