Big-O descrie cum crește timpul de execuție sau memoria unui algoritm pe măsură ce dimensiunea intrării n crește. Capturează comportamentul asimptotic worst-case, ignorând constantele și termenii de ordin inferior.
Ne pasă de rata de creștere, nu de numărarea exactă de pași. O(2n + 5) este pur și simplu O(n) pentru că pe măsură ce n devine mare, constantele și termenii mai mici nu mai au importanță.
| Big-O | Nume | Exemplu |
|---|
| O(1) | constant | array index lookup |
| O(log n) | logaritmic | binary search |
| O(n) | liniar | scanarea unei liste |
| O(n log n) | linearitmic | merge sort |
| O(n²) | pătratic | bucle imbricate |
| O(2ⁿ) | exponențial | 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 ascunde constantele: un algoritm O(n) cu o constantă uriașă poate pierde în comparație cu O(n log n) pe intrări mici. De asemenea, urmăriți complexitatea de space, nu doar time.
Big-O te permite să compari algoritmi fără a-i executa sau a te îngrijora de hardware.
Prevede care soluții supraviețuiesc atunci când intrările cresc de la sute la milioane — diferența dintre o caracteristică care se scalează și una care face timeout.
Este vocabularul pe care fiecare inginer îl folosește pentru a raționa despre performanță.