V tej vadnici boste izvedeli, kaj so asimptotični zapisi. Spoznali boste tudi zapis Big-O, zapis Theta in zapis Omega.
Učinkovitost algoritma je odvisna od časa, prostora za shranjevanje in drugih virov, potrebnih za izvajanje algoritma. Učinkovitost se meri s pomočjo asimptotičnih zapisov.
Algoritem morda ne bo imel enake zmogljivosti za različne vrste vhodov. S povečanjem vhodne velikosti se bo zmogljivost spremenila.
Študija spremembe zmogljivosti algoritma s spremembo vrstnega reda vhodne velikosti je opredeljena kot asimptotična analiza.
Asimptotični zapisi
Asimptotični zapisi so matematični zapisi, ki se uporabljajo za opis časa delovanja algoritma, ko vhod teži k določeni vrednosti ali omejevalni vrednosti.
Na primer: pri razvrščanju oblačkov je čas, ko je vhodna matrika že razvrščena, čas, ki ga algoritem porabi, linearen, tj. Najboljši primer.
Ko pa je vhodno polje v obratnem stanju, algoritem vzame največ časa (kvadratno), da razvrsti elemente, tj. Najslabši primer.
Ko vhodna matrika ni razvrščena niti v obratnem vrstnem redu, potem traja povprečen čas. Ta trajanja so označena z uporabo asimptotičnih zapisov.
Obstajajo predvsem trije asimptotični zapisi:
- Zapis Big-O
- Omega zapis
- Theta zapis
Velik zapis O (zapis O)
Zapis Big-O predstavlja zgornjo mejo časa delovanja algoritma. Tako daje najslabšo možno zapletenost algoritma.
Big-O daje zgornjo mejo funkcije
O (g (n)) = (f (n): obstajajo pozitivne konstante c in n 0, tako da je 0 ≦ f (n) ≦ cg (n) za vse n ≧ n 0 )
Zgornji izraz lahko opišemo kot funkcijo, ki f(n)pripada množici, O(g(n))če obstaja pozitivna konstanta c, ki leži med 0in cg(n)za dovolj veliko n.
Za katero koli vrednost nčas delovanja algoritma ne presega časa, ki ga določa O(g(n)).
Ker podaja najslabši čas delovanja algoritma, se pogosto uporablja za analizo algoritma, saj nas vedno zanima najslabši možni scenarij.
Omega zapis (Ω-zapis)
Omega zapis predstavlja spodnjo mejo časa delovanja algoritma. Tako zagotavlja najboljšo zapletenost algoritma.
Omega daje spodnjo mejo funkcije
Ω (g (n)) = (f (n): obstajajo pozitivne konstante c in n 0, tako da je 0 ≦ cg (n) ≦ f (n) za vse n ≧ n 0 )
Zgornji izraz lahko opišemo kot funkcijo, ki f(n)pripada množici, Ω(g(n))če obstaja pozitivna konstanta c, ki leži zgoraj cg(n), za dovolj veliko n.
Za katero koli vrednost nje najmanjši čas, ki ga zahteva algoritem, podan Omega Ω(g(n)).
Zapis Theta (Θ-zapis)
Zapis teta zajema funkcijo od zgoraj in spodaj. Ker predstavlja zgornjo in spodnjo mejo časa delovanja algoritma, se uporablja za analizo povprečne zapletenosti algoritma.
Theta omejuje funkcijo znotraj faktorjev konstant
Za funkcijo g(n), Θ(g(n))se izračuna po povezavi:
Θ (g (n)) = (f (n): obstajajo pozitivne konstante c 1 , c 2 in n 0, tako da je 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) za vse n ≧ n 0 )
Zgornji izraz lahko opišemo kot funkcijo, ki f(n)pripada množici, Θ(g(n))če obstajajo pozitivne konstante in je takšna, da jo je mogoče stisniti med in za dovolj velik n.c1c2c1g(n)c2g(n)
Če je funkcija f(n)nekje vmes in za vse , naj bi bila asimptotično tesno vezana.c1g(n)c2g(n)n ≧ n0f(n)
