U ovom vodiču naučit ćete što su asimptotski zapisi. Također, naučit ćete o Big-O notaciji, Theta notaciji i Omega notaciji.
Učinkovitost algoritma ovisi o količini vremena, pohrane i ostalih resursa potrebnih za izvršavanje algoritma. Učinkovitost se mjeri uz pomoć asimptotskih zapisa.
Algoritam možda neće imati iste performanse za različite vrste ulaza. S povećanjem veličine ulaza, izvedba će se promijeniti.
Proučavanje promjene u izvedbi algoritma s promjenom redoslijeda ulazne veličine definirano je kao asimptotska analiza.
Asimptotski zapisi
Asimptotski zapisi su matematički zapisi koji se koriste za opisivanje vremena izvođenja algoritma kada ulaz teži određenoj vrijednosti ili ograničenju.
Na primjer: U razvrstavanju oblačića, kada je ulazni niz već sortiran, vrijeme koje algoritam uzima linearno je, tj. Najbolji slučaj.
Ali, kada je ulazni niz u obrnutom stanju, algoritmu je potrebno maksimalno vrijeme (kvadratno) za sortiranje elemenata, tj. Najgori slučaj.
Kada ulazni niz nije sortiran ni obrnutim redoslijedom, potrebno je prosječno vrijeme. Ta su trajanja označena asimptotskim zapisima.
Uglavnom postoje tri asimptotska zapisa:
- Oznaka Big-O
- Omega notacija
- Theta notacija
Big-O notacija (O-notacija)
Oznaka Big-O predstavlja gornju granicu vremena izvođenja algoritma. Dakle, daje najgoru moguću složenost algoritma.
Big-O daje gornju granicu funkcije
O (g (n)) = (f (n): postoje pozitivne konstante c i n 0 takve da 0 ≦ f (n) ≦ cg (n) za sve n ≧ n 0 )
Gornji izraz može se opisati kao funkcija koja f(n)pripada skupu O(g(n))ako postoji pozitivna konstanta ctakva da se nalazi između 0i cg(n), za dovoljno veliku n.
Za bilo koju vrijednost n, vrijeme izvođenja algoritma ne prelazi vrijeme koje pruža O(g(n)).
Budući da daje vrijeme rada algoritma u najgorem slučaju, široko se koristi za analizu algoritma jer nas uvijek zanima najgori slučaj.
Omega notacija (Ω-notacija)
Omega notacija predstavlja donju granicu vremena rada algoritma. Dakle, pruža najbolju složenost slučaja algoritma.
Omega daje donju granicu funkcije
Ω (g (n)) = (f (n): postoje pozitivne konstante c i n 0 takve da je 0 ≦ cg (n) ≦ f (n) za sve n ≧ n 0 )
Gornji izraz može se opisati kao funkcija koja f(n)pripada skupu Ω(g(n))ako postoji pozitivna konstanta ctakva da leži gore cg(n), za dovoljno veliku n.
Za bilo koju vrijednost n, minimalno vrijeme potrebno algoritmu daje Omega Ω(g(n)).
Theta notacija (Θ-notacija)
Theta notacija zatvara funkciju odozgo i odozdo. Budući da predstavlja gornju i donju granicu vremena izvođenja algoritma, koristi se za analizu složenosti algoritma u prosječnom slučaju.
Theta ograničava funkciju unutar čimbenika konstanti
Za funkciju g(n), Θ(g(n))dana je izrazom:
Θ (g (n)) = (f (n): postoje pozitivne konstante c 1 , c 2 i n 0 takve da 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) za sve n ≧ n 0 )
Gornji izraz može se opisati kao funkcija koja f(n)pripada skupu Θ(g(n))ako postoje pozitivne konstante i takva da se može ugurati između i , za dovoljno velik n.c1c2c1g(n)c2g(n)
Ako funkcija f(n)leži negdje između i za sve , tada se kaže da je asimptotski tijesno vezana.c1g(n)c2g(n)n ≧ n0f(n)
