Izpitno vprašanje RAČ2PRA 15000

Iz MaFiRaWiki

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

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

Naslednja različica →
Vrstica 7: Vrstica 7:
1) Iskanje minimalnega elementa z Direktnim iskanjem (zaporednim primerjanjem): 1) Iskanje minimalnega elementa z Direktnim iskanjem (zaporednim primerjanjem):
- <java>+<java>
- direktno_iskanje_min(int[]a, int n){+direktno_iskanje_min(int[]a, int n){
- int min = a[0];+int min = a[0];
- for(int i = 0; i < n; i++){+for(int i = 0; i < n; i++){
- if(a[i] < min){+ if(a[i] < min){
- min = a[i];+ min = a[i];
- }}}</java>+}}}</java>
-Časovna zahtevnost: +Č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). 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: 2) Iskanje minimalnega elementa z Metodo Deli in vladaj:
- <java>+<java>
- deli_vladaj_min(int[]a, int zacetek, int konec, min){+deli_vladaj_min(int[]a, int zacetek, int konec, min){
- //Ce imamo le en element v tabeli:+//Ce imamo le en element v tabeli:
- if(zacetek = konec){+if(zacetek = konec){
- min = a[zacetek]; //ali a[konec] + min = a[zacetek]; //ali a[konec]}
- }+else{
- else{+ int sredina = (zacetek + konec)/2;
- int sredina = (zacetek + konec)/2;+ //rekurzivno poklicemo metodo Deli in vladaj in na vsakem delu posebej poiščemo minimalni element
- //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, zacetek, sredina, min_levo);+ deli_vladaj_min(a, sredina+1, konec, min_desno);
- deli_vladaj_min(a, sredina+1, konec, min_desno); + if(min_levo < min_desno){
- if(min_levo < min_desno){+ min = min_levo;
- min = min_levo;+ }
- }+ else{
- else{ + min = min_desno;
- min = min_desno;+
}}}</java> }}}</java>
 +
 +ČASOVNA ZAHTEVNOST:

Različica od 16:01, 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. else{
  7. int sredina = (zacetek + konec)/2;
  8. //rekurzivno poklicemo metodo Deli in vladaj in na vsakem delu posebej poiščemo minimalni element
  9. deli_vladaj_min(a, zacetek, sredina, min_levo);
  10. deli_vladaj_min(a, sredina+1, konec, min_desno);
  11. if(min_levo < min_desno){
  12. min = min_levo;
  13. }
  14. else{
  15. min = min_desno;
  16. }}}

ČASOVNA ZAHTEVNOST:

Osebna orodja