Что обозначает n в Big O Notation?

В Big O Notation n обозначает размер входных данных алгоритма. Это ключевая переменная, используемая для описания того, как время выполнения или потребление памяти алгоритма масштабируется с ростом объема данных.

Основные классы сложности:

• O(1) — Константная: Время выполнения не зависит от n. Например, доступ к элементу хеш-таблицы (объекта) по ключу.
• O(n) — Линейная: Время выполнения растет пропорционально n. Классический пример — перебор массива.
• O(n²) — Квадратичная: Время выполнения пропорционально квадрату n. Характерно для алгоритмов с вложенными циклами.

Примеры на Node.js:

// O(n) — линейный поиск
function findIndex(arr, target) {
  for (let i = 0; i < arr.length; i++) { // Цикл зависит от длины arr (n)
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

// O(n²) — проверка всех пар элементов
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) { // Внешний цикл: O(n)
    for (let j = i + 1; j < arr.length; j++) { // Внутренний цикл: O(n)
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}

Анализ через n позволяет объективно сравнивать алгоритмы и выбирать оптимальный для больших наборов данных.