1.kolokvij 2015/2016
Select messages from
# through # FAQ
[/[Print]\]

Forum@DeGiorgi -> Oblikovanje i analiza algoritama

#1: 1.kolokvij 2015/2016 Autor/ica: slonic~tonic PostPostano: 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: vsegoLokacija: /sbin/init PostPostano: 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 PostPostano: 13:42 pet, 13. 11. 2015
    —
Što sve ulazi u prvi kolokvij? Do kuda je profesor stigao s predavanjima?

#4:  Autor/ica: slonic~tonic PostPostano: 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 PostPostano: 15:00 sub, 21. 11. 2015
    —
jel se zna kad bi trebali biti rezultati?

#6:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 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.

Powered by phpBB © 2001,2002 phpBB Group
Theme created by Vjacheslav Trushkin