Как уменьшить сложность с O(n²) до O(n)?

Что означает сложность O(n²) и O(n)?

Сложность O(n²) означает, что время выполнения алгоритма растёт пропорционально квадрату размера входных данных. Это типично для вложенных циклов, где для каждого элемента массива выполняется проход по всем остальным. O(n) — линейная сложность, когда количество операций прямо пропорционально размеру данных.

Как перейти от O(n²) к O(n)?

Основной способ — использовать структуры данных с быстрым доступом, такие как хеш-таблицы (объекты, Map, Set). Вместо того чтобы для каждого элемента искать пару перебором, можно запоминать уже просмотренные элементы и проверять условие за O(1).

Пример: поиск двух чисел, дающих заданную сумму

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

// O(n) — с использованием хеш-таблицы
function twoSumFast(arr, target) {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (map.has(complement)) return [map.get(complement), i];
    map.set(arr[i], i);
  }
}

Другие техники

• Два указателя — для отсортированных массивов можно двигать указатели с разных сторон, избегая вложенных циклов.
• Скользящее окно — для задач с подмассивами фиксированной длины или условиями.
• Предварительная сортировка — иногда сортировка за O(n log n) позволяет затем применить линейный проход.

Вывод

Снижение сложности с O(n²) до O(n) достигается заменой вложенных циклов на структуры данных с константным доступом. Это особенно полезно при работе с большими объёмами данных, где квадратичные алгоритмы становятся неприемлемо медленными. Всегда стоит анализировать, можно ли избежать полного перебора пар.