Big-O описывает, как время выполнения или память алгоритма растут по мере роста размера входа n. Она описывает худший случай асимптотического поведения, игнорируя константы и члены низшего порядка.
Нас интересует скорость роста, а не точное количество шагов. O(2n + 5) — это просто O(n), потому что по мере роста n константы и меньшие члены перестают иметь значение.
| Big-O | Название | Пример |
|---|
| O(1) | константа | array index lookup |
| O(log n) | логарифмическая | binary search |
| O(n) | линейная | сканирование списка |
| O(n log n) | линеарифмическая | merge sort |
| O(n²) | квадратичная | вложенные циклы |
| O(2ⁿ) | экспоненциальная | naive subsets |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O скрывает константы: алгоритм O(n) с огромной константой может проиграть O(n log n) на малых входах. Также отслеживайте сложность по памяти, а не только по времени.
Big-O позволяет сравнивать алгоритмы без их запуска и беспокойства об оборудовании.
Она предсказывает, какие решения остаются в строю, когда входные данные растут со сотен до миллионов — разница между функцией, которая масштабируется, и той, которая зависает.
Это язык, которым каждый инженер рассуждает о производительности.