|
[quote="Ryssa"]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 :)[/quote]
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. :D
| 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  |
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. 
|
