re:re:actable
Урок 023 минуты чтения

Что такое Big O notation?

На этой странице
Кратко

Big O notation описывает, как растет время работы или потребление памяти алгоритма при увеличении размера входных данных. Это не точное время в миллисекундах, а модель роста.

Вопрос

Что такое Big O notation и зачем оценивать сложность алгоритма?

Зачем нужен Big O?

Если массив содержит 10 элементов, почти любое решение быстрое. Но если элементов миллион, разница между O(n) и O(n^2) становится огромной.

Big O помогает ответить:

Что будет с алгоритмом, когда input станет большим?

Насколько велика разница?

Посчитаем примерное число операций для разных размеров input:

Сложностьn = 10n = 1 000n = 1 000 000
O(1)111
O(log n)~3~10~20
O(n)101 0001 000 000
O(n log n)~33~10 000~20 000 000
O(n^2)1001 000 0001 000 000 000 000
O(2^n)1 024число с ~300 цифрами-

Компьютер делает порядка 100 миллионов простых операций в секунду. Значит, на миллионе элементов O(n log n) отработает за доли секунды, а O(n^2) - за несколько часов. Именно поэтому на собеседовании просят улучшить решение с O(n^2), даже если на маленьком примере оно работает мгновенно.

Частые сложности

СложностьПример
O(1)доступ по индексу
O(log n)binary search
O(n)один проход по массиву
O(n log n)хорошая сортировка
O(n^2)два вложенных цикла
O(2^n)перебор подмножеств
O(n!)перебор перестановок

Пример O(n)

function includes(nums: number[], target: number): boolean {
  for (const num of nums) {
    if (num === target) return true
  }
 
  return false
}

В худшем случае нужно проверить все элементы.

Пример O(n^2)

function hasPairWithSum(nums: number[], target: number): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return true
    }
  }
 
  return false
}

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

Почему отбрасывают константы?

O(2n) упрощают до O(n).

Big O описывает рост, а не точное количество операций. При больших n линейный рост остается линейным.

Что отвечать на собеседовании?

Big O - это асимптотическая оценка роста времени или памяти алгоритма относительно размера input. Она показывает, как решение масштабируется. При оценке обычно отбрасывают константы и младшие члены: O(2n + 10) становится O(n), O(n^2 + n) становится O(n^2).

Что важно помнить: частые ошибки

  • Думать, что Big O показывает точное время.
  • Забывать про space complexity.
  • Автоматически считать любой вложенный цикл O(n^2), хотя размеры циклов могут быть разными.
  • Не различать best, average и worst case.
  • Игнорировать стоимость операций JS-методов.

Мини-шпаргалка

  • Big O показывает рост.
  • O(1) - не зависит от n.
  • O(log n) - делим задачу.
  • O(n) - один проход.
  • O(n log n) - сортировки и divide and conquer.
  • O(n^2) - пары элементов.

Документация

Big-O Cheat Sheet, Wikipedia: Big O notation.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам