Что такое нотация «о большом»?

Sobes Copilot

Получайте ответы в реальном времени

Ответ от нейросети

sobes.tech AI

Нотация «о большое» (Big O notation) описывает верхнюю границу сложности алгоритма — как быстро увеличивается время выполнения или объем памяти в зависимости от размера входных данных. Используется для сравнения эффективности алгоритмов.

Основные типы сложности по нотации «о большое»:

Нотация	Описание	Пример
O(1)	Постоянное время	Доступ к элементу массива по индексу
O(log n)	Логарифмическое время	Бинарный поиск
O(n)	Линейное время	Поиск элемента в несортированном списке
O(n log n)	Лине-логарифмическое	Быстрая сортировка (в среднем)
O(n²)	Квадратичное время	Сортировка пузырьком
O(2ⁿ)	Экспоненциальное время	Решение задачи о коммивояжере методом грубой силы

Пример анализа сложности:

// Пример O(1)
function getFirstElement(arr) {
  return arr[0]; // Доступ по индексу занимает постоянное время, независимо от размера arr
}

// Пример O(n)
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) { // Цикл выполняется n раз, где n - длина массива
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

// Пример O(n^2)
function multiplyMatrices(matrixA, matrixB) {
  const n = matrixA.length;
  const result = [];
  for (let i = 0; i < n; i++) { // Первый цикл (n итераций)
    result[i] = [];
    for (let j = 0; j < n; j++) { // Второй цикл (n итераций)
      let sum = 0;
      for (let k = 0; k < n; k++) { // Третий цикл (n итераций)
        sum += matrixA[i][k] * matrixB[k][j];
      }
      result[i][j] = sum;
    }
  }
  return result;
}

Нотация «о большое» позволяет абстрагироваться от конкретной машины и константных множителей, фокусируясь на росте сложности при увеличении размера данных. Это помогает выбрать наиболее подходящий алгоритм для решения задачи, особенно при работе с большими объемами данных.