Что такое нотация 'О большой' и как она используется в программировании?

Нотация O большое (Big O notation) описывает верхнюю границу времени выполнения или объема памяти алгоритма в зависимости от размера входных данных (n). Она позволяет оценить масштабируемость алгоритма при росте входных данных. Применяется для сравнения эффективности алгоритмов и выбора наиболее подходящего решения для конкретной задачи.

Часто встречающиеся классы сложности:

• O(1): Постоянное время. Время выполнения не зависит от размера входных данных.
• O(log n): Логарифмическое время. Время выполнения растет медленнее, чем размер входных данных (например, бинарный поиск).
• O(n): Линейное время. Время выполнения прямо пропорционально размеру входных данных (например, простой перебор массива).
• O(n log n): Линейно-логарифмическое время. Распространено в эффективных алгоритмах сортировки (например, быстрая сортировка, сортировка слиянием).
• O(n^2): Квадратичное время. Время выполнения пропорционально квадрату размера входных данных (например, сортировка пузырьком).
• O(2^n): Экспоненциальное время. Время выполнения растет очень быстро с увеличением размера входных данных (часто в задачах перебора всех подмножеств).

Примеры:

Перебор массива:

// O(n)
function findElement(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return true;
    }
  }
  return false;
}

Бинарный поиск:

// O(log n)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Таблица сравнения роста: