Izpitno vprašanje RAČ2PRA 15000

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 15:39, 8 april 2007
Skalan (Pogovor | prispevki)

← Prejšnja različica
Različica od 15:57, 8 april 2007
Skalan (Pogovor | prispevki)

Naslednja različica →
Vrstica 5: Vrstica 5:
==Odgovor:== ==Odgovor:==
 +
 +1) Iskanje minimalnega elementa z Direktnim iskanjem (zaporednim primerjanjem):
 + <java>
 + direktno_iskanje_min(int[]a, int n){
 + int min = a[0];
 + for(int i = 0; i < n; i++){
 + if(a[i] < min){
 + min = a[i];
 + }}}</java>
 +
 +Časovna zahtevnost:
 +Z zanko for gremo čez n elementov. V zanki naredimo n-1 primerjanj. Ker nas zanima le vodilni člen, je torej časovna zahtevnost enaka O(n).
 +
 +2) Iskanje minimalnega elementa z Metodo Deli in vladaj:
 + <java>
 + deli_vladaj_min(int[]a, int zacetek, int konec, min){
 + //Ce imamo le en element v tabeli:
 + if(zacetek = konec){
 + min = a[zacetek]; //ali a[konec]
 + }
 + else{
 + int sredina = (zacetek + konec)/2;
 + //rekurzivno poklicemo metodo Deli in vladaj in na vsakem delu posebej poiščemo minimalni element
 + deli_vladaj_min(a, zacetek, sredina, min_levo);
 + deli_vladaj_min(a, sredina+1, konec, min_desno);
 + if(min_levo < min_desno){
 + min = min_levo;
 + }
 + else{
 + min = min_desno;
 + }}}</java>

Različica od 15:57, 8 april 2007

GFDL Avtor tega članka je študent/ka Skalan.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje:

Analiziraj časovno zahtevnost iskanja minimalnega elementa z direktnim iskanjem (zaporedno primerjanje) in z metodo Deli in vladaj.

Odgovor:

1) Iskanje minimalnega elementa z Direktnim iskanjem (zaporednim primerjanjem):

  1.  
  2. direktno_iskanje_min(int[]a, int n){
  3. int min = a[0];
  4. for(int i = 0; i < n; i++){
  5. if(a[i] < min){
  6. min = a[i];
  7. }}}

Časovna zahtevnost: Z zanko for gremo čez n elementov. V zanki naredimo n-1 primerjanj. Ker nas zanima le vodilni člen, je torej časovna zahtevnost enaka O(n).

2) Iskanje minimalnega elementa z Metodo Deli in vladaj:

  1.  
  2. deli_vladaj_min(int[]a, int zacetek, int konec, min){
  3. //Ce imamo le en element v tabeli:
  4. if(zacetek = konec){
  5. min = a[zacetek]; //ali a[konec]
  6. }
  7. else{
  8. int sredina = (zacetek + konec)/2;
  9. //rekurzivno poklicemo metodo Deli in vladaj in na vsakem delu posebej poiščemo minimalni element
  10. deli_vladaj_min(a, zacetek, sredina, min_levo);
  11. deli_vladaj_min(a, sredina+1, konec, min_desno);
  12. if(min_levo < min_desno){
  13. min = min_levo;
  14. }
  15. else{
  16. min = min_desno;
  17. }}}
Osebna orodja