Stranica 1 od 1

Kompleksnost koda – O i Ω notacija

PostPoslato: Utorak, 13. Jun 2017, 11:58
od korisnicko_ime
Za sledeći kod, odrediti najbližu gornju granicu kompleksnosti ([inlmath]Ο[/inlmath]) i najbližu donju granicu ([inlmath]\Omega[/inlmath]), ukoliko su ti podaci dati za funkcije [inlmath]f[/inlmath] i [inlmath]g[/inlmath], kao u tabeli i poznato je da je i u najgorem slučaju uslov ispunjen u većini slučajeva (pogledati prikačene fajlove).

im1.PNG
im1.PNG (1.51 KiB) Pogledano 841 puta

Kôd: Obeleži sve
for (int i = n; i >= 0; i/=2)
    if (f(i) <= g(i))
        for (int j = f(i)*f(i); j < n; j++)
            f(j);

Možete li objasniti kako se određuju ove kompleksnosti?

Re: Kompleksnost koda – O i Ω notacija

PostPoslato: Četvrtak, 15. Jun 2017, 08:54
od Herien Wolf
Pre svega razmotrimo šta je najgori slučaj.
Prva for petlja se svakako mora odraditi [inlmath]\log{n}[/inlmath] puta. Nakon toga imamo if naredbu u kojoj nam se računa [inlmath]f(i)[/inlmath] i [inlmath]g(i)[/inlmath]. Najgori slučaj je da [inlmath]\left(\forall i\in[0,n]\right)f(i)\leq g(i)[/inlmath] . Sledeća for petlja je u najgorem slučaju linearna, a to je za [inlmath]f(i)=0[/inlmath].
Stoga najgori slučaj nam je [inlmath]g(i)>0[/inlmath] i [inlmath]f(i)=0[/inlmath] za svako [inlmath]i\in[0,n][/inlmath]
Konačno složenost je [inlmath]\log{n}\bigl(f+g+n(3f)\bigr)=\log{n}\bigl(f(n+3)+g\bigr)[/inlmath], zamenimo najgoru složenost funkcija [inlmath]f[/inlmath] i [inlmath]g[/inlmath]. [inlmath]\log{n}\bigl(\log{n}(n+3)+n\bigr)=n\log^2n+3\log^2n+n\log{n}\approx O\left(n\log^2n\right)[/inlmath]
Što se tiče [inlmath]\Omega[/inlmath] notacije [inlmath]\Omega(n\log{n})[/inlmath] radi posao.

Nadam se da je tačno :D

Napomena: Koristili smo da u najgorem slučaju uslov bude ispunjen za svako [inlmath]i\in[0,n][/inlmath] ali nama su zanimljivi samo oni koje nam reprodukuje prva for petlja. Stoga pravilno je suziti posmatran skup samo na [inlmath]\left\{n,\frac{n}{2},\frac{n}{4},\ldots,0\right\}[/inlmath]. Dakle, najgori slučaj je [inlmath]g(i)>0[/inlmath] i [inlmath]f(i)=0[/inlmath] za svako [inlmath]i\in\left\{n,\frac{n}{2},\frac{n}{4},\ldots,0\right\}[/inlmath]