Как оценить сложность алгоритма решения задачи с маршрутами

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

Умеете ли вы посчитать сложность собственного кода, а не назвать заученную формулу. На фронтенд-собеседовании под «маршрутами» чаще всего имеют в виду задачу про билеты: дан неупорядоченный массив перелётов {from, to}, нужно восстановить путь. Следом просят улучшить решение или найти в нём скрытый квадрат.

Как отвечать

Сначала уточните постановку, от неё зависит оценка. Затем разберите решение по шагам и сложите стоимость.

Для задачи с билетами:

• наивно: для каждого города искать следующий билет перебором массива. Это вложенный цикл, O(n²) по времени;
• через Map: один проход строит словарь from → to, второй складывает пункты прибытия в Set и находит стартовый город, которого среди них нет, третий идёт по цепочке. Три линейных прохода дают O(n) по времени и O(n) по памяти.

Если маршрут это кратчайший путь в графе:

• BFS: граф без весов, O(V + E);
• Дейкстра: веса неотрицательные, с двоичной кучей O((V + E) log V). В JavaScript нет встроенной очереди с приоритетом, и если искать минимум перебором массива, выйдет O(V²). Для плотного графа это нормально, для разреженного нет;
• *поиск `A`**: та же Дейкстра с эвристикой. На картах обычно быстрее на практике, но худший случай тот же.

Проговаривайте стоимость встроенных методов, это и есть ответ на вопрос «как оценить». includes, indexOf и find у массива линейные и внутри цикла превращают O(n) в O(n²). Доступ к Map и Set в среднем константный.

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

Не считают сложность вызовов внутри цикла. Код выглядит как один for, но в нём tickets.find(...), и решение на самом деле квадратичное.

Пишут BFS с очередью на массиве и queue.shift(). По спецификации shift сдвигает все оставшиеся элементы; движки иногда это оптимизируют, но на большом графе полагаться на это не стоит. Надёжнее хранить индекс головы очереди.

Забывают про память. Словарь и множество в решении с билетами занимают O(n), и это стоит назвать самому, не дожидаясь вопроса.