junioralgorithms

Что такое нотация Big O?

Ответ

Big O описывает верхнюю границу роста времени/памяти алгоритма относительно размера входных данных. O(1) — константа, O(log n) — логарифм, O(n) — линейное, O(n²) — квадратичное. Используется для сравнения эффективности алгоритмов.

JSJavaScriptPYPython

Примеры кода:

JSJavaScript

// O(1) — константа
function getFirst(arr) {
  return arr[0]; // всегда 1 операция
}

// O(n) — линейное
function findItem(arr, target) {
  for (const item of arr) { // n операций
    if (item === target) return item;
  }
}

// O(n²) — квадратичное
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) { // n*n
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
}