Что такое Big O notation?
На этой странице
Big O notation описывает, как растет время работы или потребление памяти алгоритма при увеличении размера входных данных. Это не точное время в миллисекундах, а модель роста.
Вопрос
Что такое Big O notation и зачем оценивать сложность алгоритма?
Зачем нужен Big O?
Если массив содержит 10 элементов, почти любое решение быстрое. Но если элементов миллион, разница между O(n) и O(n^2) становится огромной.
Big O помогает ответить:
Что будет с алгоритмом, когда input станет большим?Насколько велика разница?
Посчитаем примерное число операций для разных размеров input:
| Сложность | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
O(1) | 1 | 1 | 1 |
O(log n) | ~3 | ~10 | ~20 |
O(n) | 10 | 1 000 | 1 000 000 |
O(n log n) | ~33 | ~10 000 | ~20 000 000 |
O(n^2) | 100 | 1 000 000 | 1 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)- пары элементов.