Временная сложность O(n): полный гайд с примерами на JavaScript

Aladdin

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

Зачем нужно это знать? Потому что разница между хорошим и плохим алгоритмом может быть в миллионы раз. Обработка данных за 0.1 секунду или за час — результат одного неправильного выбора алгоритма.

Как считается сложность

Сложность O(n) означает: количество операций примерно равно n (количеству элементов).

При n = 100: операций ~100
При n = 1000: операций ~1000
При n = 1 000 000: операций ~1 000 000

Линейная зависимость — просто и предсказуемо.

Пример 1: Простой цикл по массиву

function findMax(arr) {
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  
  return max;
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6];
console.log(findMax(numbers)); // 9

Почему O(n)? Цикл for проходит по всем элементам массива ровно один раз. Если в массиве 8 элементов — 8 итераций. Если 1000 элементов — 1000 итераций. Это и есть O(n).

Как это работает:

Берём первый элемент как начальное максимальное значение
Проходим по остальным элементам
Если текущий элемент больше максимума — обновляем максимум
Возвращаем результат

Пример 2: Поиск элемента в массиве

function search(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

const colors = ['red', 'green', 'blue', 'yellow'];
console.log(search(colors, 'blue'));    // 2
console.log(search(colors, 'purple'));  // -1

Почему O(n)? В худшем случае (элемент в конце или отсутствует) нужно проверить все элементы.

В лучшем случае: O(1) — элемент в начале, нашли сразу.
В среднем случае: O(n) — примерно на середине.
В худшем случае: O(n) — элемента нет или в конце.

Обычно говорят о худшем случае, поэтому это O(n).

Пример 3: Суммирование всех элементов

function sum(arr) {
  let total = 0;
  
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  
  return total;
}

const prices = [100, 250, 50, 300];
console.log(sum(prices)); // 700

Почему O(n)? Нужно посетить каждый элемент ровно один раз, чтобы добавить его к сумме. Нет способа посчитать сумму без обхода всех элементов.

Пример 4: Фильтрация массива

function filterPositive(arr) {
  const result = [];
  
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) {
      result.push(arr[i]);
    }
  }
  
  return result;
}

const numbers = [-5, 10, -3, 8, 0, -1, 15];
console.log(filterPositive(numbers)); // [10, 8, 15]

Почему O(n)? Проходим по всем элементам один раз, проверяем условие для каждого.

То же самое для встроенного метода:

const positive = numbers.filter(x => x > 0); // Тоже O(n)

Встроенные методы .filter(), .map(), .forEach() — все они O(n), потому что внутри есть цикл по всем элементам.

Пример 5: Подсчёт вхождений элемента

function countOccurrences(arr, target) {
  let count = 0;
  
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      count++;
    }
  }
  
  return count;
}

const items = ['apple', 'banana', 'apple', 'cherry', 'apple'];
console.log(countOccurrences(items, 'apple')); // 3

Почему O(n)? Нужно проверить все элементы, чтобы посчитать их правильно.

Пример 6: Проверка содержимого (includes)

function contains(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return true;
    }
  }
  return false;
}

const fruits = ['apple', 'banana', 'cherry'];
console.log(contains(fruits, 'banana'));  // true
console.log(contains(fruits, 'orange'));  // false

То же самое с методом:

fruits.includes('banana'); // Тоже O(n)

Пример 7: Копирование массива

function copyArray(arr) {
  const copy = [];
  
  for (let i = 0; i < arr.length; i++) {
    copy.push(arr[i]);
  }
  
  return copy;
}

const original = [1, 2, 3];
const duplicate = copyArray(original);
console.log(duplicate); // [1, 2, 3]

Почему O(n)? Нужно посетить каждый элемент, чтобы скопировать его.

Пример 8: Поиск минимума и максимума одновременно

function findMinMax(arr) {
  let min = arr[0];
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  
  return { min, max };
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6];
console.log(findMinMax(numbers)); // { min: 1, max: 9 }

Почему O(n)? Один цикл по всем элементам. Неважно, что операций внутри цикла больше одной — мы проходим каждый элемент один раз.

Пример 9: Сложное условие в цикле (всё ещё O(n))

function processData(arr) {
  let result = 0;
  
  for (let i = 0; i < arr.length; i++) {
    // Много операций, но всё равно O(n)
    if (arr[i] > 0) {
      result += arr[i] * 2;
      result = Math.sqrt(result);
      result += arr[i];
    } else {
      result -= arr[i];
    }
  }
  
  return result;
}

console.log(processData([1, 2, 3]));   // O(n)
console.log(processData([1, 2, 3, 4, 5])); // Примерно в 1.67 раз дольше

Почему O(n)? Важен количество итераций цикла, не количество операций внутри. Даже если внутри 100 операций, это всё ещё O(n), только с большей константой.

Пример 10: Вложенные циклы (это НЕ O(n)!)

// НЕПРАВИЛЬНО для O(n):
function findPairs(arr) {
  const pairs = [];
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] + arr[j] === 10) {
        pairs.push([arr[i], arr[j]]);
      }
    }
  }
  
  return pairs;
}

console.log(findPairs([3, 7, 2, 8, 5])); // Вложенные циклы = O(n²), НЕ O(n)

Это O(n²), а не O(n)! Если в массиве 1000 элементов, будет 1 000 000 итераций. Это качественно иначе, чем 1000 итераций.

O(n) vs O(n²): реальное сравнение

Давайте увидим разницу:

// O(n) — хороший алгоритм
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(n²) — плохой алгоритм
function quadraticSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[j] === target) return j;
    }
  }
  return -1;
}

// Тест времени
const bigArray = Array.from({length: 10000}, (_, i) => i);
const target = 9999;

console.time('O(n)');
for (let k = 0; k < 1000; k++) linearSearch(bigArray, target);
console.timeEnd('O(n)');
// Примерно 20-30ms

console.time('O(n²)');
for (let k = 0; k < 10; k++) quadraticSearch(bigArray, target); // Только 10 раз!
console.timeEnd('O(n²)');
// Примерно 5000-10000ms — в 100+ раз дольше!

Видите разницу? O(n²) убивает производительность.

Практические советы

Когда вы видите один простой цикл — это обычно O(n):

for (let i = 0; i < arr.length; i++) { ... }

Когда вы видите вложенные циклы — это обычно O(n²) или хуже:

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) { ... }
}

Встроенные методы и их сложность:

.find(), .filter(), .map(), .forEach() — O(n)
.includes(), .indexOf() — O(n)
.sort() — O(n log n) (не O(n), но лучше чем O(n²))
.push() на конец массива — O(1)
.shift(), .unshift() на начало массива — O(n) (нужно сдвигать элементы)

Почему O(n) — часто хороший выбор

O(n) часто является оптимальным решением, потому что:

Нужно посетить все элементы. Если вам нужна информация о всех элементах (сумма, поиск элемента, фильтрация), вы не можете быстрее, чем O(n).
Это масштабируется. 1 млн элементов за 100ms вполне приемлемо.
Просто для понимания. Один цикл легче отладить и понять, чем сложные структуры данных.

Заключение

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

Запомните:

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