Для чего используется n в Big O Notation?

Для чего используется n в Big O Notation

Big O Notation — это способ выражения временной и пространственной сложности алгоритма. n — это размер входных данных (input size).

Основная концепция

n представляет количество элементов, которые обрабатывает алгоритм.

// n = количество элементов в массиве
function findSum(arr: number[]): number {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {  // Итерируем n раз
    sum += arr[i];
  }
  return sum;
}

findSum([1, 2, 3]);              // n = 3, выполнится 3 итерации
findSum([1, 2, 3, ..., 1000]);   // n = 1000, выполнится 1000 итераций

Big O описывает, как время/память растёт в зависимости от n:

• O(1) — константное время, независимо от n
• O(n) — линейное время, пропорционально n
• O(n²) — квадратичное время, пропорционально n в квадрате
• O(log n) — логарифмическое время
• O(n log n) — линейно-логарифмическое время

Примеры сложности с разными значениями n

O(1) — Constant time

// Время выполнения НЕ зависит от n
function getFirstElement(arr: any[]): any {
  return arr[0];  // Всегда одна операция, независимо от длины массива
}

n = 10:     время = 1 операция
n = 1000:   время = 1 операция
n = 1M:     время = 1 операция

O(n) — Linear time

// Время зависит линейно от n
function findMax(arr: number[]): number {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {  // Итерируем n раз
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

n = 10:     время = 10 операций
n = 1000:   время = 1000 операций
n = 1M:     время = 1M операций
// Время растёт пропорционально n

O(n²) — Quadratic time

// Вложенные циклы
function bubbleSort(arr: number[]): number[] {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

n = 10:     время = 10 * 10 = 100 операций
n = 1000:   время = 1000 * 1000 = 1M операций
n = 1M:     время = 1M * 1M = 1T операций (!)
// Время растёт квадратично — очень медленно для больших n

O(log n) — Logarithmic time

// Binary search
function binarySearch(arr: number[], target: number): number {
  let left = 0, 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;  // Каждая итерация сокращает область поиска в 2
  }
  return -1;
}

n = 10:       время = log(10) ≈ 3-4 операции
n = 1000:     время = log(1000) ≈ 10 операций
n = 1M:       время = log(1M) ≈ 20 операций
// Очень эффективно для больших данных

O(n log n) — Linearithmic time

// Efficient sorting algorithms (merge sort, quick sort)
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  
  return merge(left, right);  // O(n log n) total
}

n = 10:     время = 10 * log(10) ≈ 33 операции
n = 1000:   время = 1000 * log(1000) ≈ 10,000 операций
n = 1M:     время = 1M * log(1M) ≈ 20M операций
// Хороший баланс между быстротой и масштабируемостью

Сравнение сложностей

// Визуализация роста времени при увеличении n

n = 100:
  O(1)      = 1
  O(log n)  = 7
  O(n)      = 100
  O(n log n) = 700
  O(n²)     = 10,000
  O(2ⁿ)     = 1.27e30 (невозможно!)

n = 1,000:
  O(1)      = 1
  O(log n)  = 10
  O(n)      = 1,000
  O(n log n) = 10,000
  O(n²)     = 1,000,000
  O(2ⁿ)     = невозможно

n = 10,000:
  O(1)      = 1
  O(log n)  = 13
  O(n)      = 10,000
  O(n log n) = 130,000
  O(n²)     = 100,000,000
  O(2ⁿ)     = невозможно

Практические примеры в Node.js

O(1) — быстро всегда:

// Array access
const arr = [1, 2, 3];
console.log(arr[100]);  // Один lookup, O(1)

// Object property access
const obj = {a: 1, b: 2};
console.log(obj.a);  // Один lookup, O(1)

// Set/Map get
const map = new Map();
map.get('key');  // O(1)

O(n) — медленнее при росте n:

// Array filter, map, find
const filtered = arr.filter(x => x > 5);  // O(n)
const mapped = arr.map(x => x * 2);       // O(n)
const found = arr.find(x => x === 5);     // O(n)

// String operations
const s = 'hello world';
console.log(s.includes('world'));  // O(n) где n = длина строки

O(log n) — очень эффективно:

// Binary search
function search(sortedArr: number[], target: number): boolean {
  let left = 0, right = sortedArr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArr[mid] === target) return true;
    if (sortedArr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}

O(n²) — очень медленно для больших n:

// Nested loops
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    // O(n²) operations
  }
}

// Даже если оптимизировать внутренний цикл
for (let i = 0; i < n; i++) {
  for (let j = i; j < n; j++) {  // Starts from i
    // Still O(n²) because (n + (n-1) + (n-2) + ... + 1) = n(n+1)/2 ≈ O(n²)
  }
}

Как анализировать сложность

Правило 1: Счёт операций

function example(arr: number[]) {
  const n = arr.length;
  
  let sum = 0;           // 1 операция
  for (let i = 0; i < n; i++) {  // n итераций
    sum += arr[i];       // 1 операция per iteration
  }
  console.log(sum);      // 1 операция
  
  // Total: 1 + n + 1 = n + 2 операций
  // Big O: O(n) — игнорируем константы
}

Правило 2: Вложенные структуры = умножение

for (let i = 0; i < n; i++) {         // n итераций
  for (let j = 0; j < n; j++) {       // n итераций для каждого i
    console.log(i, j);                // O(1) операция
  }
}
// Total: n * n = O(n²)

Правило 3: Последовательные структуры = сложение

for (let i = 0; i < n; i++) {         // n итераций, O(n)
  console.log(i);
}

for (let j = 0; j < n; j++) {         // n итераций, O(n)
  console.log(j);
}
// Total: O(n) + O(n) = O(2n) = O(n)

Рекомендации

• O(1), O(log n) — отличная производительность, используй
• O(n), O(n log n) — хорошо, часто необходимо
• O(n²), O(n³) — опасайся для больших n
• O(2ⁿ), O(n!) — избегай в production

Вывод: n в Big O Notation — это размер входных данных. Big O показывает, как алгоритм масштабируется при растущем n. Для выбора алгоритма всегда анализируй его Big O сложность.