Что такое Big O Notation (нотация «О» большое)?

Big O Notation — это математическая нотация, описывающая асимптотическую сложность алгоритма. Она показывает, как время выполнения или потребление памяти алгоритма растёт с увеличением объёма входных данных (обычно обозначаемого как n) в худшем случае.

Основные классы сложности с примерами на Node.js/JavaScript:

• O(1) — Константная сложность. Время выполнения не зависит от размера входных данных.

  // Доступ к элементу массива по индексу или к свойству объекта по ключу.
  const arr = [10, 20, 30];
  console.log(arr[0]); // O(1)
  
  const user = { id: 1, name: 'Alice' };
  console.log(user.name); // O(1)

• O(n) — Линейная сложность. Время выполнения растёт линейно с ростом n.

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

• O(n²) — Квадратичная сложность. Характерна для алгоритмов с вложенными циклами.

  // Сравнение всех пар элементов (наивная сортировка пузырьком).
  function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {         // O(n)
      for (let j = 0; j < arr.length - 1; j++) { // O(n) -> Итог: O(n²)
        if (arr[j] > arr[j + 1]) {
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
      }
    }
    return arr;
  }

• O(log n) — Логарифмическая сложность. Характерна для алгоритмов, которые на каждом шаге делят задачу пополам (например, бинарный поиск).

Использование Big O позволяет объективно сравнивать эффективность алгоритмов и выбирать оптимальные решения для обработки больших данных.