Big-O descrive come il tempo di esecuzione o la memoria di un algoritmo crescono al crescere della dimensione dell'input n. Cattura il comportamento asintotico nel caso peggiore, ignorando le costanti e i termini di ordine inferiore.
Ci interessa il tasso di crescita, non il numero esatto di step. O(2n + 5) è semplicemente O(n) perché man mano che n cresce, le costanti e i termini più piccoli smettono di importare.
| Big-O | Nome | Esempio |
|---|---|---|
| O(1) | costante | accesso a indice array |
| O(log n) | logaritmica | ricerca binaria |
| O(n) | lineare | scansione di una lista |
| O(n log n) | lineare-logaritmica | merge sort |
| O(n²) | quadratica | cicli annidati |
| O(2ⁿ) | esponenziale | sottoinsiemi ingenui |
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 nasconde le costanti: un algoritmo O(n) con una costante enorme può perdere rispetto a O(n log n) su input piccoli. Traccia anche la complessità dello spazio, non solo il tempo.
Big-O ti permette di confrontare algoritmi senza eseguirli e senza preoccuparti dell'hardware.
Prevede quali soluzioni sopravvivono quando gli input crescono da centinaia a milioni — la differenza tra una funzionalità che scala e una che va in timeout.
È il vocabolario che ogni ingegnere utilizza per ragionare sulla performance.