| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
slonic~tonic
Forumaš(ica)
Pridružen/a: 26. 10. 2011. (14:16:34)
Postovi: (84)16
Spol: 
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: 
Lokacija: /sbin/init
|
 Postano: 15:16 pet, 30. 10. 2015 Naslov: |
    |
|
|
Uputa za a):[list][*] vanjska petlja se izvrsava za [tt]i = 1,2,...,n[/tt], dakle [b][tt]n[/tt] puta[/b];
[*] unutrasnja petlja se izvrsava za [tt]j = n, n/2, n/4,..., 1[/tt], sto znaci da za [tex]n[/tex] izmedju [tex]2^k[/tex] i [tex]2^{k+1}-1[/tex] imamo [tex]n = 2^k + r_1, 2^{k-1} + r_2, ..., 2^0[/tex], tj. [tex]k+1 = \lceil \lg(n+1) \rceil \approx \bf \lg n[/tex] [b]koraka[/b];
[*] Ukupno: pomnozi to dvoje jer je petlja u petlji.[/list:u]
Za b) ide slicno.
Uputa za a):- vanjska petlja se izvrsava za i = 1,2,...,n, dakle n puta;
- unutrasnja petlja se izvrsava za j = n, n/2, n/4,..., 1, sto znaci da za [tex]n[/tex] izmedju [tex]2^k[/tex] i [tex]2^{k+1}-1[/tex] imamo [tex]n = 2^k + r_1, 2^{k-1} + r_2, ..., 2^0[/tex], tj. [tex]k+1 = \lceil \lg(n+1) \rceil \approx \bf \lg n[/tex] koraka;
- Ukupno: pomnozi to dvoje jer je petlja u petlji.
Za b) ide slicno.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
slonic~tonic
Forumaš(ica)
Pridružen/a: 26. 10. 2011. (14:16:34)
Postovi: (84)16
Spol:
|
| Postano: 21:03 pet, 13. 11. 2015 Naslov: |
|
|
|
Zanima me slozenost 4.zadatka kolokvija: https://web.math.pmf.unizg.hr/~singer/oaa/oaa_0809/2008_k1.pdf
napisala sam algoritam: (koji samo vraća broj elemenata presjeka)
[code:1]int presjek (a, b, n) {
k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
while(i<n & j<n) {
if(a[i]==b[j]) { k++, i++, j++ }
else if(a[i]>b[j]) j++
i++
}
return k;
}
[/code:1]
Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ??
Zanima me slozenost 4.zadatka kolokvija: https://web.math.pmf.unizg.hr/~singer/oaa/oaa_0809/2008_k1.pdf
napisala sam algoritam: (koji samo vraća broj elemenata presjeka)
| Kod: | int presjek (a, b, n) {
k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
while(i<n & j<n) {
if(a[i]==b[j]) { k++, i++, j++ }
else if(a[i]>b[j]) j++
i++
}
return k;
}
|
Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ??
_________________
Lakše je naučiti matematiku nego raditi bez nje.
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
| Postano: 15:38 sub, 21. 11. 2015 Naslov: |
|
|
|
[quote="slonic~tonic"][code:1]int presjek (a, b, n) {
k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
while(i<n & j<n) {
if(a[i]==b[j]) { k++, i++, j++ }
else if(a[i]>b[j]) j++
i++
}
return k;
}
[/code:1][/quote]
Cini mi se da bi [tt]i++[/tt] trebao biti u nekakvom [tt]else[/tt] bloku. (Ostalo ne komentiram, jer mi se cini da je to nekakav pseudo, a ne pravi C)
[quote="slonic~tonic"]Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ??[/quote]
Obicno se broje aritmeticke operacije. Korak petlje, ovako kako je kod tebe napisano, ima izmedju jednog i cetiri poziva [tt]++[/tt], dakle izmedju [tex]O(n)[/tex] i [tex]O(4n)[/tex], sto je -- naravno -- jednako [tex]O(n)[/tex].
@Gost: Ne znam, ali vjerojatno ne jako brzo jer je profesor do kraja iduceg tjedna na sluzbenom putu.
| slonic~tonic (napisa): | | Kod: | int presjek (a, b, n) {
k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
while(i<n & j<n) {
if(a[i]==b[j]) { k++, i++, j++ }
else if(a[i]>b[j]) j++
i++
}
return k;
}
|
|
Cini mi se da bi i++ trebao biti u nekakvom else bloku. (Ostalo ne komentiram, jer mi se cini da je to nekakav pseudo, a ne pravi C)
| slonic~tonic (napisa): | | Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ?? |
Obicno se broje aritmeticke operacije. Korak petlje, ovako kako je kod tebe napisano, ima izmedju jednog i cetiri poziva ++, dakle izmedju [tex]O(n)[/tex] i [tex]O(4n)[/tex], sto je – naravno – jednako [tex]O(n)[/tex].
@Gost: Ne znam, ali vjerojatno ne jako brzo jer je profesor do kraja iduceg tjedna na sluzbenom putu.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
|
