Izpitno vprašanje RAČ2PRA 3800

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 11:28, 23 april 2006
UrsaSaksida (Pogovor | prispevki)
Odgovor
← Prejšnja različica
Različica od 14:27, 8 april 2007
Skalan (Pogovor | prispevki)
Odgovor
Naslednja različica →
Vrstica 11: Vrstica 11:
* Primer programa z linearno in kvadratno časovno zahtevnostjo in izračunom trajanja izvajanja najdemo pri izpitnem vprašanju [[Izpitno vprašanje RAČ2PRA 4000|4000]]. * Primer programa z linearno in kvadratno časovno zahtevnostjo in izračunom trajanja izvajanja najdemo pri izpitnem vprašanju [[Izpitno vprašanje RAČ2PRA 4000|4000]].
 +
 +Primer:
 + Dana sta dva algoritma. Dejanska časovna zahtevnost naj bo:
 +
 + T1(n) = n^2 – 95
 + T2(n) = n^2 / 100 + 4
 + Oba: O(n^2)
 +
 + T1(10) = 5, T2(10) = 5
 + T1(30) = 805, T2(30) = 13
 + T1(90) = 8005, T2(90) = 85
 + T1(180) = 32305, T2(180) = 328
 + T1(360) = 129505, T2(360) = 1300
 +
 +Kljub temu, da je časovna zahtevnost v obeh primerih kvadratna, se rezultati zelo razlikujejo. In to je le eden izmed mnogih primerov, ki dokazuje, da iz podatka, ki ga prikazuje O-notacija, ne moremo sklepati prav dosti.
[[Kategorija:Izpitno vprašanje]] [[Kategorija:Izpitno vprašanje]]
[[Kategorija:Računalništvo 2 (UL-FMF Praktična matematika)]] [[Kategorija:Računalništvo 2 (UL-FMF Praktična matematika)]]

Različica od 14:27, 8 april 2007

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

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.

Predmet Računalništvo 2 (FMF PRA)

Vprašanje

Dan imaš algoritem kvadratne časovne zahtevnosti. Ali lahko iz podatka, da za obdelavo 100 podatkov algoritem porabi 10s sklepamo, koliko časa bo obdeloval 1000 podatkov? Odgovor obrazloži!

Odgovor

  • Iz danih podatkov ne moremo sklepati, koliko časa bo program obdeloval 1000 podatkov. Pri časovni zahtevnosti upoštevamo le prevladujoči del, ki je v tem primeru kvadratni, O(n2). Lahko bi program vseboval tudi linearni del. Tako bi se npr. linearni del izvajal 3 sekunde, kvadratni pa 7 sekund. Iz danih podatkov tako ne morem izračunati, koliko časa bi potekala obravnava 1000 podatkov.
  • Primer programa z linearno in kvadratno časovno zahtevnostjo in izračunom trajanja izvajanja najdemo pri izpitnem vprašanju 4000.


Primer:

Dana sta dva algoritma. Dejanska časovna zahtevnost naj bo:

T1(n) = n^2 – 95
T2(n) = n^2 / 100 + 4
Oba: O(n^2)

T1(10) = 5,       T2(10) = 5
T1(30) = 805,     T2(30) = 13 
T1(90) = 8005,    T2(90) = 85
T1(180) = 32305,  T2(180) = 328
T1(360) = 129505, T2(360) = 1300

Kljub temu, da je časovna zahtevnost v obeh primerih kvadratna, se rezultati zelo razlikujejo. In to je le eden izmed mnogih primerov, ki dokazuje, da iz podatka, ki ga prikazuje O-notacija, ne moremo sklepati prav dosti.

Osebna orodja