Восемь типичных классов роста — это «алфавит» сложности. Каждый мы запоминаем на примере.
Порядок классов
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Полиномиальные классы считаются практичными; 2ⁿ и n! пригодны лишь для малых n.
| Класс | Пример |
|---|---|
O(1) | доступ по индексу, поиск в dict |
O(log n) | бинарный поиск в отсортированном списке |
O(n) | один проход по списку, максимум |
O(n log n) | сортировка слиянием, sorted |
O(n²) | два вложенных цикла, все пары |
O(n³) | наивное умножение матриц |
O(2ⁿ) | все подмножества множества |
O(n!) | все перестановки |
import math
def steps(n):
return {
"O(1)": 1,
"O(log n)": math.ceil(math.log2(n)),
"O(n)": n,
"O(n log n)": n * math.ceil(math.log2(n)),
"O(n^2)": n ** 2,
"O(n^3)": n ** 3,
"O(2^n)": 2 ** n,
"O(n!)": math.factorial(n),
}
for name, value in steps(10).items():
print(f"{name:<11}{value:>10,}")O(1) 1
O(log n) 4
O(n) 10
O(n log n) 40
O(n^2) 100
O(n^3) 1,000
O(2^n) 1,024
O(n!) 3,628,800