Izpitno vprašanje RAČ2PRA 15000

Iz MaFiRaWiki

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

Č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 reda n, oziroma O(n).


2) Iskanje minimalnega elementa z Metodo Deli in vladaj:

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

ČASOVNA ZAHTEVNOST: Če imamo v tabeli n elementov, se v prvi zanki izvede n-1 primerjanj, prav tako v drugi. Časovna zahtevnost je spet O(n).

Osebna orodja