Чем отличаются типы сложности алгоритмов и как это влияет на код?

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

Типы сложности (от лучшего к худшему)

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

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

Выбор структуры данных

// O(n²): вложенный поиск в массиве
for (const a of arr) if (other.includes(a)) {} // includes O(n)

// O(n): хеш-таблица
const set = new Set(other);
for (const a of arr) if (set.has(a)) {} // has O(1)

Понимание сложности подсказывает использовать Map/Set вместо вложенных циклов.

Масштабируемость

• O(n) на 1000 элементов — быстро; O(n²) — заметно; O(2ⁿ) — зависнет.
• Код, работающий на малых данных, может «умереть» на больших.

Оптимизация

• Мемоизация (экспонента → полином).
• Правильный алгоритм (бинарный поиск вместо линейного).
• Избегать вложенных циклов там, где можно хеш.

На собеседовании

Оценка сложности решения — стандартное требование.

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

Типы сложности: O(1) (константа — идеал), O(log n) (бинарный поиск), O(n) (проход), O(n log n) (сортировки), O(n²) (вложенные циклы — проблема), O(2ⁿ) (перебор — критично). Влияет на код: понимание подсказывает использовать Map/Set (O(1)) вместо вложенных циклов (O(n²)), мемоизацию, правильные алгоритмы, иначе код «умирает» на больших данных.