Алгоритмическая сложность и Big O

Зачем это фронтендеру?

На собеседованиях в 2026 году всё чаще спрашивают не только React, но и алгоритмы. Понимание Big O помогает:

• Оценить, «тормозит» ли твой код при росте данных
• Выбрать правильный подход к задаче
• Пройти алгоритмическую секцию собеседования

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

---

Что такое Big O?

Big O (нотация «О большое») — способ описать, как растёт время выполнения алгоритма (или потребление памяти) при увеличении объёма входных данных.

n — это размер входных данных. Например, количество элементов в массиве.

Big O описывает худший случай — максимальное количество операций, которое может потребоваться.

Аналогия

Представь, что ты ищешь книгу в библиотеке:

---

Основные типы сложностей

O(1) — Константное время

Одна операция, независимо от размера данных.

const first = arr[0];
const map = new Map();
map.set("key", "value");
map.get("key");

Где встречается в фронтенде: доступ к элементу массива по индексу, чтение/запись в Map/Set, доступ к свойству объекта.

---

O(log n) — Логарифмическое время

На каждом шаге отбрасывается часть данных (обычно половина).

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Где встречается: бинарный поиск, Map.has() в некоторых реализациях, работа с отсортированными данными.

Важно: бинарный поиск работает только на отсортированных данных.

---

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;
}

Где встречается: Array.prototype.find(), filter(), map(), reduce(), любой цикл по массиву.

---

O(n log n) — Линеарифмическое время

Обычно это сортировка + проход по данным.

Где встречается: Array.prototype.sort() в JavaScript (использует Timsort — O(n log n)), merge sort, быстрая сортировка в среднем случае.

---

O(n²) — Квадратное время

Два вложенных цикла. При n = 1000 — миллион операций.

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Где встречается: вложенные циклы по одному массиву, наивные алгоритмы сортировки (bubble sort, selection sort).

Это типичный «красный флаг» на собеседовании. Почти всегда можно оптимизировать до O(n).

---

O(2ⁿ) — Экспоненциальное время

Количество операций удваивается с каждым новым элементом.

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Где встречается: наивная рекурсия, перебор всех подмножеств. При n > 40 уже заметно тормозит.

---

Пространственная сложность (Space Complexity)

Помимо времени, оценивают память — сколько дополнительной памяти требует алгоритм.

// O(1) по памяти — разворачиваем массив на месте
function reverseInPlace(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
}

// O(n) по памяти — создаём новый массив
function reverseNew(arr) {
  return [...arr].reverse();
}

---

Шпаргалка

---

Типичные задачи с собеседований

Задача 1. Two Sum

Дан массив чисел и целевая сумма. Найти индексы двух чисел, дающих в сумме target.

Плохое решение — O(n²):

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
}

Хорошее решение — O(n):

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
}

Суть оптимизации: вместо второго цикла используем Map для хранения уже увиденных значений. Map.has() и Map.get() работают за O(1), поэтому общая сложность — O(n).

---

Задача 2. Проверка на дубликаты

Есть ли в массиве повторяющиеся элементы?

Плохо — O(n²):

function hasDuplicate(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):

function hasDuplicate(arr) {
  return new Set(arr).size !== arr.length;
}

---

Задача 3. Подсчёт частоты символов

Посчитать, сколько раз каждый символ встречается в строке.

Решение — O(n):

function charFrequency(str) {
  const freq = {};
  for (const char of str) {
    freq[char] = (freq[char] || 0) + 1;
  }
  return freq;
}

Это O(n) по времени и O(k) по памяти, где k — количество уникальных символов.

---

Задача 4. Палиндром

Проверить, является ли строка палиндромом.

Решение — O(n):

function isPalindrome(str) {
  let left = 0, right = str.length - 1;
  while (left < right) {
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }
  return true;
}

Два указателя — один из начала, другой из конца. Сходятся к середине. O(n) по времени, O(1) по памяти.

---

Задача 5. Поиск пропущенного числа

В массиве от 1 до n пропущено одно число. Найти его.

Решение — O(n):

function findMissing(arr, n) {
  const expectedSum = (n * (n + 1)) / 2;
  const actualSum = arr.reduce((sum, num) => sum + num, 0);
  return expectedSum - actualSum;
}

Используем формулу суммы арифметической прогрессии вместо сортировки или хеш-таблицы.

---

Как оптимизировать: паттерны

1. Заменить вложенный цикл на хеш-таблицу

// O(n²) → O(n)
const set = new Set(arr);
if (set.has(target - current)) { /* ... */ }

2. Два указателя (для отсортированных массивов)

// O(n²) → O(n)
let left = 0, right = arr.length - 1;
while (left < right) { /* сдвигаем указатели */ }

3. Скользящее окно

// O(n²) → O(n)
let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
let max = sum;
for (let i = k; i < arr.length; i++) {
  sum += arr[i] - arr[i - k];
  max = Math.max(max, sum);
}

4. Мемоизация (для рекурсии)

// O(2ⁿ) → O(n)
const memo = {};
function fib(n) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n - 1) + fib(n - 2);
  return memo[n];
}

---

Что спрашивают на собеседованиях

1. «Оцените сложность вашего решения» — всегда думай об этом до того, как начнёшь писать.
2. «Можете ли вы сделать это быстрее?» — если написал O(n²), тебя попросят оптимизировать до O(n) или O(n log n).
3. «Какой trade-off между временем и памятью?» — часто можно ускорить алгоритм, пожертвовав памятью (хеш-таблицы, мемоизация).
4. «Что будет, если массив содержит миллион элементов?» — проверка, понимаешь ли ты разницу между O(n) и O(n²) на практике.
5. Задачи на структуру данных — Map, Set, стек, очередь. Знать, какие операции за какую сложность выполняются.

Встроенные структуры данных JS и их сложность

Главное правило: если нужен частый поиск — используй Set или Map вместо массива.

---

Ресурсы для практики

• LeetCode — задачи с фильтрацией по сложности (Easy → Medium → Hard)
• NeetCode 150 — 150 задач, покрывающих все основные паттерны
• Big O Cheat Sheet — визуальная шпаргалка по сложностям