Big-O jiddeskrivi kif il-ħin tal-mgħaddija jew il-memorja ta' algoritmu tikber meta d-daqs tal-input n jikber. Taqbad il-biħavjur asintotiku tal-agħar każ, u tignora l-kostanti u t-termini ta' ordni aktar bassa.
Iridu nħarsu għal rata ta' tkabbir, mhux għad-daqs eżatt ta' passi. O(2n + 5) hija sempliċement O(n) għax meta n jikber, il-kostanti u t-termini iżgħar jieqfu jkunu importanti.
| Big-O | Isem | Eżempju |
|---|
| O(1) | kostanti | tiftix ta' indikatur ta' array |
| O(log n) | logaritmiku | tfittxija binarja |
| O(n) | lineari | skanerjar lista |
| O(n log n) | lineari-logaritmiku | merge sort |
| O(n²) | quadratiku | ħoloq inbiddla |
| O(2ⁿ) | esponenzjali | sottosettijiet 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 niħbi l-kostanti: algoritmu O(n) b'kostanti kbir tista' titlef kontra O(n log n) fuq inputs iżgħar. Ukoll isegwi l-kumplessità tal-ispazju, mhux biss tal-ħin.
Big-O tħallak tqabbel algoritmi mingħajr ma jdaħħlu jew ma tħassex dwar il-hardware.
Jippreduċi liema soluzzjonijiet jibqgħu ħajjin meta l-inputs jikbru minn mjetmiet għal miljuni — id-differenza bejn feature li teskala u waħda li ħin il-out.
Hi l-vokabolarji li kull inġinier juża biex jaraguna dwar il-prestazzjoni.