Big-O kuvaa kuinka algoritmin suoritusaika tai muisti kasvaa kun syötteen koko n kasvaa. Se kuvaa pahimman tapauksen asymptoottista käyttäytymistä jättäen huomioimatta vakiot ja alemman kertaluvun termit.
Meitä kiinnostaa kasvunopeus, ei tarkat askeleet. O(2n + 5) on yksinkertaisesti O(n) koska kun n kasvaa suureksi, vakiot ja pienemmät termit lakkaavat olemasta tärkeitä.
| Big-O | Nimi | Esimerkki |
|---|
| O(1) | vakio | taulukon indeksin haku |
| O(log n) | logaritminen | binäärihaku |
| O(n) | lineaarinen | listan skannaus |
| O(n log n) | lineariitminen | lomitus lajittelu |
| O(n²) | neliöllinen | sisäkkäiset silmukat |
| O(2ⁿ) | eksponentiaalinen | naiivit osajoukot |
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 piilottaa vakiot: O(n)-algoritmi jolla on valtava vakio voi hävitä O(n log n):lle pienillä syötteillä. Seuraa myös tilan kompleksisuutta, ei vain aikaa.
Big-O antaa sinun vertailla algoritmeja ajamatta niitä tai huolestumatta laitteistosta.
Se ennustaa mitkä ratkaisut selviytyvät kun syötteet kasvavat sadoista miljooniin — ero skaalautuvan ominaisuuden ja aikakatkaisevan välillä.
Se on sanavarasto, jota jokainen insinööri käyttää suorituskyvystä päättelemiseen.