Big-O opisuje, kako se čas izvajanja ali pomnilnik algoritma povečuje, ko se vhodna velikost n povečuje. Zajema najslabšo asimptotsko vedenje, pri čemer ignora konstante in člene nižjega reda.
Skrbimo nas rast, ne natančnih števcev korakov. O(2n + 5) je preprosto O(n), ker z rastjo n postanejo konstante in manjši členi nepomembni.
| Big-O | Ime | Primer |
|---|
| O(1) | konstantna | iskanje indeksa v polju |
| O(log n) | logaritmična | binarno iskanje |
| O(n) | linearna | skeniranje seznama |
| O(n log n) | linearitmična | merge sort |
| O(n²) | kvadratna | gnezdene zanke |
| O(2ⁿ) | eksponentna | naivne podmnožice |
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 skriva konstante: algoritem O(n) z ogromno konstanto lahko izgubi proti O(n log n) na majhnih vhodih. Prav tako sledite prostorski kompleksnosti, ne samo času.
Big-O vam omogoča primerjavo algoritmov brez njihovega izvajanja ali skrbi za strojno opremo.
Napoveduje, katera rešitev preživi, ko se vnosi povečajo od stotine do milijonov — razlika med funkcijo, ki se skalira, in eno, ki počaka.
To je besednjak, ki ga vsi inženirji uporabljajo za razmišljanje o zmogljivosti.