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

1.kolokvij 2015/2016

through

[^/[Print]\]

Forum@DeGiorgi -> Oblikovanje i analiza algoritama

#1: 1.kolokvij 2015/2016 Autor/ica: slonic~tonic,

Postano: 21:25 čet, 29. 10. 2015
—
http://web.math.pmf.unizg.hr/~singer/oaa/oaa_1415/2014_k1.pdf

Može rješenje 1.zadatka ?

#2: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 15:16 pet, 30. 10. 2015
—
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.

#3: Gradivo 1. kolokvija Autor/ica: Gost,

Postano: 13:42 pet, 13. 11. 2015
—
Što sve ulazi u prvi kolokvij? Do kuda je profesor stigao s predavanjima?

#4: Autor/ica: slonic~tonic,

Postano: 21:03 pet, 13. 11. 2015
—
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) ??

#5: Autor/ica: Gost,

Postano: 15:00 sub, 21. 11. 2015
—
jel se zna kad bi trebali biti rezultati?

#6: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 15:38 sub, 21. 11. 2015
—

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.

Forum@DeGiorgi -> Oblikovanje i analiza algoritama

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

Stranica 1 / 1.