Səkkiz tipik böyümə sinfi mürəkkəbliyin «əlifbasıdır». Hər birini bir nümunə ilə tanıyırıq.
Siniflərin sırası
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Polinomial siniflər praktik sayılır; 2ⁿ və n! yalnız kiçik n üçün yararlıdır.
| Sinif | Nümunə |
|---|---|
O(1) | siyahıda indekslə müraciət, dict axtarışı |
O(log n) | çeşidlənmiş siyahıda ikili axtarış |
O(n) | siyahını bir dəfə gəzmək, maksimum |
O(n log n) | birləşdirmə ilə çeşidləmə, sorted |
O(n²) | iki iç-içə dövr, bütün cütlər |
O(n³) | matrislərin sadə vurulması |
O(2ⁿ) | çoxluğun bütün alt çoxluqları |
O(n!) | bütün permutasiyalar |
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