Как оценить сложность решения
Вопрос
Объясни, как ты оцениваешь временную и пространственную сложность своего решения на собесе.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Называет, что такое n (и m, если входов несколько)
Считает циклы: вложенные перемножаются, последовательные складываются
Помнит скрытые циклы: includes, indexOf, slice, sort, spread
Отдельно оценивает память, включая стек рекурсии
Сравнивает с ограничениями: при n до 10⁵ O(n²) уже не годится
Что могут спросить следом
- Почему O(2n) и O(n) это одно и то же?
- Какая сложность у
arr.slice()внутри цикла? - Что такое амортизированная O(1)?
Разбор
Сначала договариваюсь, что такое n: длина массива, число вершин, длина строки. Если входов два, держу оба: O(n + m) или O(n · m). Дальше иду по коду: последовательные проходы складываются, вложенные перемножаются, деление задачи пополам даёт log n. Обязательно смотрю на скрытые циклы: includes, indexOf, slice, concat, spread и sort внутри цикла легко превращают O(n) в O(n²) или O(n² log n). Память считаю отдельно: доп. структуры вроде Map или Set и глубину рекурсии, потому что стек тоже память. Наконец сверяюсь с ограничениями: при n около 10⁵ квадрат это 10¹⁰ операций, значит нужен O(n log n) или O(n). Например, поиск пары с суммой: перебор O(n²) по времени и O(1) по памяти, с Set O(n) и O(n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.