Введение в алгоритмы и сложность

Технический фундамент анализа сложности

При оценке алгоритма полезно учитывать:

асимптотику по времени (как растет число операций);
асимптотику по памяти (как растет доп. пространство);
worst/average-case поведение;
стоимость базовых операций выбранной структуры данных.

Это дает инженерный контекст: "быстро на тесте" не равно "масштабируется в проде".

Зачем разработчику думать про алгоритмы

Алгоритм это пошаговый способ решить задачу. В коде это значит: каким образом ты ищешь, фильтруешь, сортируешь, считаешь, преобразуешь данные. Два алгоритма могут давать одинаковый результат, но один будет работать миллисекунды, а другой - секунды при росте данных.

Ключевой момент: сложность показывает, как растут время и память алгоритма при увеличении объема входа.

Проверь себя: почему код, который "быстрый" на 100 элементах, может стать медленным на 100 000?

Big O простыми словами

Big O описывает порядок роста затрат:

O(1) - константно;
O(n) - линейно;
O(n^2) - квадратично;
O(n log n) - "почти линейно", часто встречается в сортировках;
O(log n) - логарифмически.

// O(1)
function getFirst(arr) {
  return arr[0];
}

// O(n)
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

Смотри, что важно: Big O не про точные миллисекунды, а про тенденцию роста.

Пример сравнения `O(n)` и `O(n^2)`

// O(n^2): проверка дублей через двойной цикл
function hasDuplicatesSlow(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): через Set
function hasDuplicatesFast(arr) {
  return new Set(arr).size !== arr.length;
}

Дополнительный пример: trade-off памяти ради ускорения поиска.

function buildIndex(items) {
  const byId = new Map();
  for (const item of items) byId.set(item.id, item);
  return byId; // больше памяти, но быстрый get по id
}

Обе функции решают одну задачу, но масштабируются по-разному.

Проверь себя: какая версия будет лучше при миллионе элементов и почему?

Временная и пространственная сложность

Обычно смотрят два параметра:

время (time complexity) - сколько операций;
память (space complexity) - сколько дополнительной памяти.

Иногда быстрее по времени значит дороже по памяти. Например, Set ускоряет поиск дублей, но требует доп. памяти.

Это нормальный trade-off, его оценивают по контексту задачи.

Реальные микро-сценарии

Поиск пользователя по id.

Если каждый раз искать в массиве find, будет O(n). Если держать Map по id, доступ будет близок к O(1).

Фильтрация событий в аналитике.

Неправильный алгоритм на больших логах может увеличить задержку и стоимость инфраструктуры.

Проверка уникальности email на импорте CSV.

Выбор между двойным циклом и Set напрямую влияет на время загрузки.

Частые ошибки новичков

Оптимизировать "на глаз" без профилирования узких мест.
Считать, что Big O заменяет реальные замеры.
Игнорировать стоимость памяти.
Писать слишком сложную оптимизацию раньше времени.

Анти-провал: сначала реши задачу корректно, потом оптимизируй hotspot по фактам (профайлер, метрики).

Что будет, если изменить входные данные

На массиве из 20 элементов разница между O(n) и O(n^2) может быть незаметной. На 200 000 элементов квадратичный алгоритм станет узким местом. Это ключевая причина, почему анализ сложности важен даже в "обычном" JavaScript-коде.

Проверь себя: почему рост данных часто происходит незаметно до продакшена?

Краткий итог

Алгоритм это способ решения задачи, а сложность - оценка его масштабируемости.
Big O показывает, как растут затраты с увеличением входа.
Важно учитывать и время, и память.
Один и тот же результат можно получить разными по эффективности алгоритмами.
Оптимизация должна опираться на реальные узкие места, а не на догадки.

Введение в алгоритмы и сложность