Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIKA U INFORMATICI

Kompleksnost koda – O i Ω notacija

Brojni sistemi, Bulova algebra, binarna aritmetika itd.

Kompleksnost koda – O i Ω notacija

Postod korisnicko_ime » Utorak, 13. Jun 2017, 11:58

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 828 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?
Poslednji put menjao Daniel dana Utorak, 13. Jun 2017, 12:25, izmenjena samo jedanput
Razlog: Dodavanje Latex-tagova; prekucavanje koda sa slike, uz kropovanje slike – tačke 13. i 14. Pravilnika
 
Postovi: 14
Zahvalio se: 0 puta
Pohvaljen: 1 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Kompleksnost koda – O i Ω notacija

Postod Herien Wolf » Četvrtak, 15. Jun 2017, 08:54

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]
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 231
Zahvalio se: 87 puta
Pohvaljen: 213 puta


Povratak na MATEMATIKA U INFORMATICI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 16 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 09:46 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs