Урок 022 минуты чтения
Как говорить про сложность решения?
На этой странице
Кратко
Сложность нужно объяснять через размер входа и количество операций. Хороший ответ называет time complexity, space complexity, худший случай и причины, почему каждый элемент обрабатывается именно столько раз.
Вопрос
Как объяснять сложность решения на собеседовании?
Хороший формат
Пусть n - длина массива.
Мы проходим массив один раз.
Операции Map в среднем O(1).
Time complexity: O(n).
Map может хранить до n элементов.
Space complexity: O(n).Пример Two Sum
function twoSum(nums: number[], target: number): boolean {
const seen = new Set<number>()
for (const num of nums) {
if (seen.has(target - num)) return true
seen.add(num)
}
return false
}Объяснение:
n - длина nums.
Один проход по массиву: O(n).
Set.has и Set.add в среднем O(1).
Set хранит до n чисел: O(n).Для сортировки
Сначала сортируем: O(n log n).
Потом один проход: O(n).
Итог: O(n log n).Для графа
V - вершины, E - ребра.
DFS посещает каждую вершину и каждое ребро.
Time: O(V + E).
Visited хранит V вершин.
Space: O(V).Что отвечать на собеседовании?
Я называю переменные размера input, объясняю доминирующую операцию, учитываю встроенные методы и память дополнительных структур. Если есть сортировка, она часто доминирует. Если есть граф, использую V и E. Если есть рекурсия, учитываю call stack.
Что важно помнить: частые ошибки
- Просто сказать
O(n)без объяснения. - Забыть
sort. - Не учитывать
Map/Setпамять. - Не учитывать recursion stack.
- Использовать одно
nдля двух разных inputs. - Скрыть expensive method внутри цикла.
Мини-шпаргалка
- Назови
n,m,V,E. - Time - сколько операций.
- Space - дополнительные структуры.
- Sort often dominates.
- Recursion stack counts.
- Built-in methods count.
Документация
Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.