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

Что проверяют

Понимаете ли вы, что оценка про скорость роста, и умеете ли применить её к своему коду, а не только назвать классы.

Как отвечать

Сложность описывает, как растёт число операций при росте размера входа. Записывается O-нотацией и отбрасывает константы и младшие члены: важен порядок роста, а не точное число.

Классы по возрастанию: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).

Для фронтенда полезно привязать к реальным вещам:

• поиск в массиве через includes или indexOf это O(n). В цикле по массиву получается O(n²), и на тысяче элементов это уже миллион операций. Замена массива на Set даёт O(1) на проверку;
• сортировка через sort это O(n log n);
• вложенные циклы по одному и тому же списку это квадрат, самая частая причина зависаний интерфейса;
• обход дерева DOM и рекурсия по вложенным структурам пропорциональны числу узлов;
• сложность по памяти тоже считается: копия массива на каждой итерации это линейная память вместо постоянной.

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

Где спотыкаются

Называют классы, но не могут оценить сложность собственного кода.

Считают, что O(1) значит быстро: это значит независимо от размера входа.

Забывают про память и оценивают только время.

Не замечают квадратичность в связке map внутри filter по тем же данным.