re:re:actable
Урок 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.

Документация

Big-O Cheat Sheet.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам