Как определить сложность задачи?

Сложность задачи оценивают через анализ алгоритма в нотации «O большое»: сколько растут время и память с ростом входных данных. Смотрят на количество и вложенность операций.

Как определить временную сложность

1. Считать операции относительно размера входа n.
2. Отбросить константы и младшие члены — важен только доминирующий рост.

Признаки по структуре кода

• O(1) — фиксированное число операций, доступ по индексу/ключу.
• O(n) — один цикл по данным.
• O(n²) — вложенные циклы по данным.
• O(log n) — деление задачи пополам (бинарный поиск).
• O(n log n) — эффективные сортировки, «раздели и властвуй».
• O(2ⁿ) — перебор всех подмножеств, наивная рекурсия.

// O(n)
for (const x of arr) process(x);

// O(n²)
for (const a of arr) for (const b of arr) compare(a, b);

// O(log n)
while (n > 1) n = Math.floor(n / 2);

Что учитывать

• Худший/средний/лучший случай — обычно оценивают худший.
• Временную и пространственную сложность отдельно.
• Скрытая сложность встроенных методов (includes — O(n), sort — O(n log n)).

Практика

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

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

Сложность оценивают в нотации O, считая операции относительно n и отбрасывая константы: один цикл — O(n), вложенные — O(n²), деление пополам — O(log n), эффективные сортировки — O(n log n). Учитывают худший случай, время и память отдельно, скрытую сложность встроенных методов.