Что такое сложность алгоритма?

Сложность алгоритма — это оценка того, как растут время выполнения (временная сложность) и потребление памяти (пространственная) с увеличением объёма входных данных. Выражается в нотации «O большое».

Нотация O

O(...) описывает асимптотический рост при больших n, отбрасывая константы и младшие члены.

Частые классы (от лучшего к худшему)

• O(1) — константная: не зависит от размера (доступ по индексу, map.get).
• O(log n) — логарифмическая: бинарный поиск.
• O(n) — линейная: один проход по массиву.
• O(n log n) — эффективные сортировки (merge sort).
• O(n²) — квадратичная: вложенные циклы (пузырьковая сортировка).
• O(2ⁿ), O(n!) — экспоненциальная/факториальная: перебор, наивная рекурсия.

// O(n) — один проход
arr.forEach((x) => process(x));

// O(n²) — вложенные циклы
for (const a of arr) for (const b of arr) compare(a, b);

Что оценивают

• Worst / average / best case — худший, средний, лучший случай.
• Временную и пространственную сложность отдельно.

Зачем

Помогает выбрать эффективное решение и предсказать поведение на больших данных.

Коротко для собеседования

Сложность алгоритма — рост времени и памяти от размера входа в нотации O: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). Отбрасывает константы, оценивает асимптотику. Помогает выбирать эффективные алгоритмы.