Izpitno vprašanje RAČ2PRA 3800

Iz MaFiRaWiki

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