Forum@DeGiorgi :: Pogledajte temu - 1. kolokvij 2014/2015

1. kolokvij 2014/2015

through

[^/[Print]\]

Forum@DeGiorgi -> Oblikovanje i analiza algoritama

#1: 1. kolokvij 2014/2015 Autor/ica: Pero.Edin,

Postano: 17:32 čet, 13. 11. 2014
—
Do koje stranice treba znati rukom pisanu skriptu za prvi kolokvij?

Meni u biljeskama pise otprilike 62 str. (broj napisan rukom), ali nisam sigurna.

Novo poglavlje pocinje na 63. str (Kompleksnost algoritma i kompleksnost problema), cini mi se da to nismo radili.

Moze neka konkretnija informacija?

Hvala

#2: Autor/ica: sunny,

Postano: 14:13 pet, 14. 11. 2014
—
Kolega kaze sljedece:
Obrađeno iz skripte:
-Uvod u složenost: [1str , 62str]
-Ocjena same integralom (sve)
-Rekurzivni algoritmi (sve)

#3: Autor/ica: Ryssa,

Postano: 10:48 uto, 18. 11. 2014
—
Može mala pomoć oko 1. b) iz 2011. Nisam sigurna u rješenje, pa bih molila ispravak ako griješim, j-petlja se vrti i puta, k-petlja se vrti i puta, while petlja ovisi o i i izvršava se u ovisnosti broja znamenki u bazi 4 broja n ->rješenje O(n^2lgn). Nisam sigurna niti u točnost ovoga niti kako lijepo argumentirati ove rečenice Smile

#4: Autor/ica: luka_m, Lokacija: Zagreb

Postano: 23:23 uto, 18. 11. 2014
—

Ryssa (napisa):

Može mala pomoć oko 1. b) iz 2011. Nisam sigurna u rješenje, pa bih molila ispravak ako griješim, j-petlja se vrti i puta, k-petlja se vrti i puta, while petlja ovisi o i i izvršava se u ovisnosti broja znamenki u bazi 4 broja n →rješenje O(n^2lgn). Nisam sigurna niti u točnost ovoga niti kako lijepo argumentirati ove rečenice Smile

Dvije unutarnje petlje rade [tex]i^2[/tex] koraka u svakoj iteraciji vanjske petlje. Vanjska petlja se vrti [tex]log_4 n[/tex] puta. Dakle, imamo sumu za m = 1 do [tex]log_4 n[/tex], od [tex]i^2[/tex]. Stavio sam novu varijablu m, jer općenito m.-ta iteracija nema vrijednost brojač = i (jer i se mijenja eksponencijalno). No, (otprilike) vrijedi ovo: [tex]i = 4^m[/tex], pa to možemo uvrstiti umjesto [tex]i^2[/tex], pa dobijemo [tex](4^m)^2[/tex], tj [tex]4^{2m}[/tex]. Sad imamo lijepu sumu koju možemo izračunati, najbolje određenim integralom (gornja granica je [tex]log_4 n[/tex]), integral od toga je, ne gledajući asimptotski irelevantne dijelove, jednak opet [tex]4^{2m}[/tex], pa kad se uvrsti gornja granica dobije se nešto što je [tex]O(n^2)[/tex] (dakle ne tvoje rješenje).

U ocjeni sume integralom ima još par detalja na koje treba paziti poput ocjene donje granice, ali ovo je bio bitan dio a meni se žuri ići spavati. Very Happy

Forum@DeGiorgi -> Oblikovanje i analiza algoritama

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.