Big-O përshkruan se si koha e ekzekutimit ose memoria e një algoritmi rritet ndërsa madhësia e hyrjes n rritet. Ajo kap sjelljen asimptotike në rastin më të keq, duke ignoruar konstante dhe terma të rendit më të ulët.
Ne marrim parasysh shpejtësinë e rritjes, jo numrin e saktë të hapave. O(2n + 5) është thjesht O(n) sepse ndërsa n rritet, konstante dhe termat më të vegjël nuk kanë rëndësi.
| Big-O | Emri | Shembull |
|---|
| O(1) | konstante | kërkimi i indeksit në array |
| O(log n) | logaritmike | kërkimi binar |
| O(n) | lineare | skanimi i listës |
| O(n log n) | linearitmike | merge sort |
| O(n²) | kuadratike | sythe të ndërthurura |
| O(2ⁿ) | eksponenciale | nënbashkësi naïve |
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 fsheh konstante: një algoritëm O(n) me një konstante të madhe mund të humbasë ndaj O(n log n) në hyrje të vogla. Gjithashtu gjurmoni kompleksitetin e hapësirës, jo vetëm kohës.
Big-O ju lejon të krahasoni algoritme pa i ekzekutuar ato ose shqetësim për harduearin.
Ejo parashikon se cilat zgjidhje mbijetojnë kur hyrjet rriten nga qindra në miliona — diferenca midis një veçorie që shkallëzohet dhe një që arrin timeout.
Ejo është fjalori që çdo inxhinier përdor për të arsyetuar për performancën.