Big O notacija: vodič po časovni in prostorski kompleksnosti algoritmov

Zapis Big O je način primerjave algoritmov. Primerja jih tako, da izračuna, koliko pomnilnika potrebujejo in koliko časa potrebujejo za dokončanje.

Zapis Veliki O se pogosto uporablja pri določanju kompleksnosti problema, znanega tudi kot razred kompleksnosti problema. Matematik Paul Bachmann (1837-1920) je prvi uporabil ta zapis v drugi izdaji svoje knjige "Analytische Zahlentheorie" leta 1896. Edmund Landau (1877-1938) je zapis populariziral. Zato se ljudje, ko govorijo o Landaujevih simbolih, sklicujejo na ta zapis.

Zapis Big O je poimenovan po izrazu "red funkcije", ki se nanaša na rast funkcij. Zapis velikega O se uporablja za iskanje zgornje meje (najvišje možne vrednosti) stopnje rasti funkcije, kar pomeni, da ugotovi najdaljši čas, ki bo potreben za pretvorbo vhoda v izhod. To pomeni, da lahko algoritem razvrstimo v skupine glede na to, koliko časa lahko traja v najslabšem primeru, ko bo vsakič izbrana najdaljša pot.

Big O je izraz, ki ugotavlja čas izvajanja po najslabšem možnem scenariju in prikazuje, kako učinkovit je algoritem, ne da bi bilo treba program zagnati na računalniku. To je uporabno tudi zato, ker imajo lahko različni računalniki različno strojno opremo in zato za izvedbo potrebujejo različno količino časa. Ker Big O vedno predpostavlja najslabši možni scenarij, lahko pokaže dosledno merjenje hitrosti: ne glede na strojno opremo bo O ( 1 ) {\displaystyle O(1)} $O(1)$ vedno končan hitreje kot O ( n ! ) {\displaystyle O(n!)}, $O(n!)$ ker imata različne stopnje učinkovitosti.

Kaj natančno pomeni Big O?

Big O označuje asimptotično zgornjo mejo rasti funkcije glede na velikost vhoda n. Praktčno to pomeni, da nas zanima, kako čas (ali pomnilnik) poraste, ko vhod raste proti neskončnosti. Pri analizi običajno:

odstranimo konstante (npr. 2n in n imata enako stopnjo rasti);
gledamo najvišji redovni člen (npr. n^2 + n je O(n^2));
osredotočimo se na vedenje za velike vrednosti n, ne na majhne primerke.

Najpogostejše razrede časovne kompleksnosti (z razlago)

O(1) — konstanta: čas ne odvisen od velikosti vhoda. Primer: dostop do elementa tabele po indeksu.
O(log n) — logaritemska rast: primer je binarno iskanje v urejeni tabeli.
O(n) — linearna rast: en prehod čez podatke (npr. iskanje elementa brez urejenosti).
O(n log n) — tipična za učinkovite sortirne algoritemske paradigme, npr. mergesort, heapsort.
O(n^2) — kvadratna rast: pogosto pri zanko znotraj zanke (npr. osnovni bubble sort).
O(2^n) — eksponentna rast: pogosto z rekurzivnimi rešitvami vseh podmnožic (npr. problema potujočega trgovca brez optimizacij).
O(n!) — faktorijska rast: najslabše možne stopnje za permutativne probleme brez prerezov.

Časovna in prostorska kompleksnost

Poleg časovne kompleksnosti (koliko operacij) je pomembna tudi prostorska kompleksnost (koliko dodatnega pomnilnika potrebuje algoritem). Primeri:

Prostorska O(1) — in-place algoritmi, ki uporabljajo konstantno dodatnega pomnilnika (npr. zamena dveh števil v tabeli).
Prostorska O(n) — algoritem, ki potrebuje dodatno tabelo velikosti n (npr. kopija polja ali pomocna struktura pri nekaterih sortiranju).

Drugi Landaujevi simboli

Poleg Big O se pogosto uporabljata še:

Big Θ (Theta) — označuje asimptotično natančno rast (zgornja in spodnja meja hkrati). Če je algoritem Θ(n), pomeni, da v najboljšem in najslabšem primeru raste linearno.
Big Ω (Omega) — spodnja meja rasti (najmanjša stopnja rasti v nekem scenariju).

Kako analizirati kodo za Big O

Preštejte osnovne operacije v zankah: enojna zanka čez n daje O(n); gnezdene zanke dajo produkt velikosti (dve gnezdi O(n^2)).
Pri zaporednih blokih se seštevek nadomesti z največjo rastjo (O(n) + O(n^2) = O(n^2)).
Pri rekurziji uporabite rekurzivne relacije (recurrence relations), npr. T(n) = 2T(n/2) + O(n) daje O(n log n) (Master theorem).
Pri ocenjevanju prezrite konstante in nižje členke — pomemben je vodilni člen za velike n.

Specifični primeri

Binary search: O(log n) — deli prostor iskanja na pol vsak korak.
Linear search: O(n) — v najslabšem primeru preišče vse elemente.
Mergesort / Heapsort: O(n log n) — učinkoviti sortirni algoritmi za splošne primere.
Bubble sort: O(n^2) — primer neučinkovite metode za večje n.
Dinamična tabela (amortiziran push): amortizirana O(1) — posamezni vstavki so v povprečju konstantni zaradi občasne povečave velikosti.

Najpogostejše napake in nasveti

Ne zamenjujte teoretične kompleksnosti z dejanskimi meritvami: za manjše n lahko počasnejši algoritem z majhnimi konstantami deluje hitreje.
Upoštevajte prostorske omejitve — algoritem z nizko časovno, vendar visoko prostorsko kompleksnostjo morda ni primeren za vgrajene sisteme.
Pri izbiri algoritma upoštevajte tip vhodnih podatkov (povprečni primer, najslabši primer, verjetnost posebnih vzorcev).
Amortizirana kompleksnost je uporabna za podatkovne strukture, ki občasno opravijo drage operacije (npr. ponovna alokacija vektorja).

Zaključek

Zapis Big O in sorodni Landaujevi simboli omogočajo, da algoritme primerjamo neodvisno od strojne opreme in implementacijskih detajlov. Pomagajo identificirati, kateri algoritmi bodo primerni za velike podatke in kakšne so potencialne omejitve glede časa in pomnilnika. Medtem ko Big O daje pomembno teoretično oceno, je pri praktični uporabi pogosto smiselno kombinirati to analizo z merjenjem dejanske učinkovitosti na realnih podatkih.

Primeri

V vseh naslednjih primerih je uporabljena koda, napisana v Pythonu. Upoštevajte, da to ni popoln seznam tipov Big O.

Stalno

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Vedno traja enako dolgo ne glede na vhodne podatke. Vzemimo na primer funkcijo, ki sprejme celo število (imenovano x) in vrne dvojno vrednost:

def double(x): return x * 2 #Vrni vrednost x krat 2

Po sprejetju vhodnega podatka bo ta funkcija vedno naredila en korak in vrnila izhodni podatek. Je konstantna, ker bo vedno potrebovala enako količino časa, torej je O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Linearno

O ( n ) {\displaystyle O(n)} $O(n)$ . Poveča se glede na velikost vhoda, ki ga predstavlja n {\displaystyle n} . Predpostavimo, da funkcija sprejme n in vrne vsa števila od 1 do n:

def count(n): i = 1 #Izdelaj števec "i" z vrednostjo 1 while i <= n: #Ker je i manjši ali enak n print(i) #Prikaz vrednosti i = i + 1 #Predefiniraj i kot "vrednost i + 1"

Če bi vnesli vrednost 5, bi se izpisalo 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} $1,2,3,4,5$ za dokončanje je potrebnih 5 zank. Podobno, če bi vnesli vrednost 100, bi se izpisalo 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , kar bi zahtevalo 100 zank. Če je vhodnih podatkov n {\displaystyle n}, potem je čas izvajanja algoritma vsakič natanko n {\displaystyle n} zank, torej je O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktorialni

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Povečuje se v faktorskih količinah, kar pomeni, da se potreben čas močno povečuje z vnosom. Recimo, da želimo obiskati pet mest po svetu in si ogledati vse možne razvrstitve (permutacije). Algoritem, ki ga lahko napišemo z uporabo Pythonove knjižnice itertools, je naslednji:

uvoz itertools #Uvoz knjižnice itertools cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Mrežo naših izbranih mest def permutations(cities): #Za vhodno polje mest: for i in itertools. permutations(cities): #Za vsako permutacijo naših elementov (pripisano spremenljivki "i") print(i) #Izhod i

Ta algoritem bo izračunal vsako edinstveno permutacijo naših mest in jo nato prikazal. Primeri rezultatov bodo vključevali:

("London", "Pariz", "Berlin", "Amsterdam", "Rim") ("London", "Pariz", "Berlin", "Rim", "Amsterdam") ("London", "Pariz", "Amsterdam", "Berlin", "Rim") ... ("Rim", "Amsterdam", "Pariz", "Berlin", "London") ("Rim", "Amsterdam", "Berlin", "London", "Pariz") ("Rim", "Amsterdam", "Berlin", "Pariz", "London")

Tu je naš seznam vnosov dolg 5 elementov in za vsako izbiro se naše preostale možnosti zmanjšajo za 1. Z drugimi besedami, naših 5 vnosov izbere 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ elementov (ali 5 ! {\displaystyle 5!} $5!$ ). Če je naš vhod dolg n {\displaystyle n} mest, potem je število izhodov n ! {\displaystyle n! } $n!$ ; z drugimi besedami, ob predpostavki, da gremo skozi vse permutacije, bomo za dokončanje potrebovali O ( n ! ) {\displaystyle O(n!)} $O(n!)$ zank.

Zapis Little-o

Strožja različica Velikega O je little-o. Razlika med velikim O in little-o je v tem, da je little-o stroga zgornja meja: medtem ko O ( n ) {\displaystyle O(n)} $O(n)$ pomeni, da se bo čas dokončanja glede na velikost vhoda povečal na to največjo vrednost, pa o ( n ) {\displaystyle o(n)} $o(n)$ pomeni, da bo čas dokončanja na splošno pod to vrednostjo. Z drugimi besedami, Big O predvideva, da bo vsaka zanka ubrala najdaljšo pot in da bo proces trajal čim dlje, medtem ko je little-o bolj realističen glede dejanskega časa izvajanja; če število zank temelji na metanju šeststranske kocke, Big O vedno predvideva, da je padla številka 6, medtem ko little-o upošteva enako verjetnost padca drugih števil.

Vprašanja in odgovori

V: Kaj je zapis Big O?

O: Zapis Big O je način primerjave hitrosti rasti različnih funkcij, ki se pogosto uporablja za primerjavo učinkovitosti različnih algoritmov z izračunom, koliko pomnilnika in časa je potrebnega za dokončanje. Uporablja se lahko tudi za ugotavljanje, kako zapleten je problem.

V: Kdo je prvi uporabil ta zapis?

O: Matematik Paul Bachmann (1837-1920) je prvi uporabil ta zapis v svoji knjigi "Analytische Zahlentheorie" leta 1896.

V: Kaj pomeni Big O?

O: Big O pomeni "red funkcije", ki se nanaša na stopnjo rasti funkcij.

V: Kako se uporablja Big O?

O: Zapis Big O se uporablja za iskanje zgornje meje (najvišje možne vrednosti) za stopnjo rasti funkcije, kar pomeni, da se določi najdaljši čas, ki bo potreben za pretvorbo vhoda v izhod. To pomeni, da lahko algoritme razvrstimo v skupine glede na to, koliko časa potrebujejo v najslabšem možnem primeru, pri čemer bo vsakič izbrana najdaljša pot.

V: Kaj so Landauovi simboli?

O: Simboli Landau se nanašajo na zapis Big O, poimenovan po Edmundu Landauu (1877-1938), ki je populariziral ta zapis.

V: Zakaj je Big O uporaben?

O:Big O nam omogoča merjenje hitrosti, ne da bi nam bilo treba izvajati programe na računalnikih, saj vedno predvideva najslabše možne scenarije, zaradi česar je konsistenten ne glede na razlike v strojni opremi med računalniki. Pokaže tudi, kako učinkovit je algoritem, ne da bi ga bilo treba dejansko zagnati na računalniku.