> Как определить сложность метода (JavaScript)

Короткий ответ

Сложность метода определяется через анализ количества операций относительно размера входных данных. Используем Big O нотацию: O(1), O(n), O(n²), O(log n) и т.д. Для этого выделяем доминирующий цикл или рекурсию, игнорируем константы и младшие члены. В JavaScript важно учитывать скрытые операции: spread, map/filter/reduce, конкатенацию строк, работу с Set/Map.

Подход к решению

1. Определяем входные данные и их размер (n - длина массива, строки, количество элементов).
2. Ищем циклы, рекурсию, вложенные структуры.
3. Считаем количество итераций в худшем случае.
4. Упрощаем: убираем константы, оставляем только доминирующий член.
5. Учитываем скрытые операции: методы массивов (forEach, map, filter - O(n)), вложенные вызовы, spread внутри цикла.
6. Для рекурсии - строим дерево вызовов, считаем глубину и количество ветвлений.

Пример кода

JAVASCRIPT
// O(n) - один проход
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(n²) - вложенный цикл
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// O(n log n) - сортировка
function sortAndFilter(arr) {
  return arr.sort((a, b) => a - b).filter(x => x > 0);
}

// Скрытая O(n²) - spread в цикле
function buildMatrix(n) {
  const result = [];
  for (let i = 0; i < n; i++) {
    result.push([...Array(n).fill(i)]); // spread - O(n)
  }
  return result;
}

Edge cases

• Пустой массив или null - метод может упасть, но сложность не меняется.
• Объекты с большим количеством ключей - доступ к свойству O(1), но Object.keys() - O(n).
• Строки: конкатенация в цикле - O(n²), лучше использовать массив и join.
• Set/Map: has/get - O(1) в среднем, но при коллизиях - O(n).
• Рекурсия с мемоизацией - сложность может стать O(n) вместо O(2ⁿ).
• Вложенные вызовы методов: arr.filter(x => arr.includes(x)) - O(n²).

Как отвечать на собеседовании

Начни с вопроса: "Какой размер входных данных?" - это показывает понимание контекста. Затем объясни алгоритм словами, выдели доминирующую операцию. Не называй сложность сразу - сначала покажи ход рассуждений. Упомяни worst case и average case, если они отличаются. Для JavaScript обязательно скажи про скрытые операции - это отличает senior от junior. Если метод использует встроенные функции, уточни их сложность (например, sort - O(n log n) в V8). Закончи примером, как можно улучшить сложность.

Что проверяет интервьюер

• Понимание Big O, а не заучивание формул.
• Умение анализировать код, а не только писать.
• Знание специфики JavaScript: методы массивов, spread, строки, Set/Map.
• Способность объяснить trade-off между временной и пространственной сложностью.
• Внимание к edge cases и скрытым операциям.
• Умение рассуждать о реальных сценариях: когда O(n²) приемлемо, а когда нет.