> Как измеряется и описывается сложность алгоритмов (JavaScript)

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

Сложность алгоритмов описывается через Big O нотацию - асимптотическую верхнюю границу роста времени выполнения или памяти в зависимости от размера входных данных. Измеряется в терминах операций: O(1), O(log n), O(n), O(n log n), O(n²) и т.д. Для frontend-разработчика важно понимать сложность операций с массивами, объектами, DOM-манипуляциями и рекурсией. Практически измеряется через профилирование (performance.now(), Chrome DevTools), но теоретически - через анализ кода.

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

На собеседовании оценивают не только знание определений, но и умение применять Big O к реальным задачам. Основные шаги:

1. Определить входные данные и их размер (n).
2. Найти доминирующую операцию (циклы, рекурсия, вложенные структуры).
3. Упростить выражение: отбросить константы и младшие члены.
4. Различать best/average/worst case (обычно говорят про worst).
5. Учитывать пространственную сложность (дополнительная память).

Для JavaScript важно помнить: методы массивов (map, filter, reduce) - O(n), поиск в объекте - O(1) в среднем, но вложенные циклы дают O(n²). Рекурсия может дать O(2^n) без мемоизации.

Пример кода

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 hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(n) с пространственной сложностью O(n) - через Set
function hasDuplicatesOptimized(arr) {
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

// O(log n) - бинарный поиск
function binarySearch(sortedArr, target) {
  let left = 0, right = sortedArr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Edge cases

• Пустые массивы или null - проверять до вычислений.
• Сортированные vs неотсортированные данные - бинарный поиск требует сортировки.
• Рекурсия с глубокой вложенностью - риск stack overflow (в Node.js лимит ~10k вызовов).
• Методы вроде Array.prototype.sort() - в V8 использует TimSort, сложность O(n log n), но для почти отсортированных данных может быть O(n).
• Объекты с числовыми ключами - V8 может хранить их как массивы, что меняет сложность доступа.
• Строки - конкатенация в цикле даёт O(n²) из-за неизменяемости, лучше использовать массив и join.

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

Начни с определения Big O и её смысла - верхняя граница роста. Приведи примеры из реальной frontend-разработки: рендер списка (O(n)), поиск по DOM (O(n) в среднем), debounce/throttle (O(1) по времени). Покажи, как упрощать выражение: 3n² + 5n + 2 → O(n²). Обязательно упомяни пространственную сложность - интервьюеры часто спрашивают про trade-off между временем и памятью. Если дают задачу - сначала озвучь сложность наивного решения, потом оптимизацию. Не бойся сказать "не знаю" про редкие нотации (Θ, Ω) - для senior важно практическое применение, а не теория.

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

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