Izpitno vprašanje RAČ2PRA 2600

Iz MaFiRaWiki

Vprašanje

Ugotovi in primerjaj časovno in prostorsko zahtevnost dveh algoritmov za izračun potence števila: z zaporednim množenjem in z razpolavljanjem

Odgovor

Z zaporednim množenjem in z razpolavljanjem:

- Algoritem z zaporednim množenjem:

Izračunati želimo bn. To storimo tako, da novo spremenljivko p nastavimo na 1.0 in za i = 1, …, n, ponavljaj množenje p = p * b. Končaj z odgovorom p.

Zapis v javi

  1.  
  2. static double poten1 (double b, int n)
  3. {
  4. if (n==0) return 1;
  5. double p = 1.0;
  6. for(int i=1; i<=n; i++) p=p*b;
  7. return p;
  8. }

Pri analizi gre za štetje množenj, kar je najbolj karakteristična operacija. Množenj je n. Časovna zahtevnost je reda n. To zapišemo kot O(n). Prostorska zahtevnost O(2) dodatnega prostora (dve dodatni spremenljivki).

- Algoritem z razpolavljanjem:

Ideja: b1000 = b500 * b500, če poznamo b500 lahko b1000 izračunamo le z enim dodatnim množenjem.

Algoritem

Postavi p na 1.

2. Dokler je n > 1, ponavljaj:

2.1. Če je n lih, množi p s b.

2.2. Razpolovi n (morebitni ostanek zavrzi).

2.3. Množi b s samim seboj.

3. Pomnoži b s p in končaj z odgovorom p.

Zapis v javi

  1.  
  2. static double poten2 (double b, int n) // Vrne b^n (kjer je n ne-negativen)
  3. {
  4. if (n==0) return 1;
  5. double p = 1.0;
  6. while(n > 1)
  7. {
  8. if (n % 2 != 0) p = p * b; // množenje s b
  9. n = n / 2; b = b * b; // podvojimo
  10. }
  11. p=p*b;
  12. return p;
  13. }

Pri analizi gre za štetje množenj. Na korakih 2.1 do 2.3 izvedemo največ 2 množenji. Korake ponovimo toliko-krat, kot lahko n razpolovimo – floor(log2n) + 1 krat. Časovna zahtevnost je reda log n. To zapišemo kot O(log n). Prostorska zahtevnost O(1) dodatnega prostora (ena dodatna spremenljivka).

Zakluček:

Algoritem......................Časovna zahtevnost..............Prostorska zahtevnost

- z zaporednim množenjem..............O(n)............................O(2)..........

- z razpolavljanjem...................O(log n)........................O(1)..........


Torej je algoritem z razpolavljanjem boljši v obeh primerih.

Osebna orodja