Izpitno vprašanje RAČ2PRA 4000

Iz MaFiRaWiki

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

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

Imamo program, katerega čas izvajanja je O(n2), ima pa tudi nezanemarljiv del, ki potrebuje za izvajanje konstanten čas. Ko smo program pognali pri n = 10, je tekel 97 sekund, ko smo ga pognali pri n = 20, je tekel 100 sekund.
Kako dolgo bi program delal za n = 1000?
Za problem iz prejnjega dela smo uspeli najti postopek, ki je O(n).
Del programa, ki se izvaja konstanten čas, je enak.
Program smo pognali pri n = 1000 in je delo opravil v 1096 sekundah.
Oba postopka želimo sestaviti tako, da bomo za določene n uporabljali prejšnji (kvadratni) postopek, za druge pa novega (linearnega). Kako?

Odgovor

Nalogo razdelima na dva dela in jo tako rešujemo:
1. Imamo torej podana dva podatka, s katerima izračunamo splošno funkcijo, ki jo imamo. Matematično se lotimo naloge takole: Določiti je potrebno konstanti a in b, funkcija se glasi f1(n) = a*(n^2) + b, kar vidimo iz teksta naloge, ker program potrebuje O(n^2) in O(n). Poleg tega imamo podana še dva podatka in sicer f1(10) = 97 in f1(20) = 100. Iz teh podatkov določimo konstanti a in b. Torej izračun naj bi se glasil takole: Iz prvega podatka dobimo
100a + b = 97
400a + b = 100
Rešimo sistem dveh enačb z dvema neznankama, dobimo:
a = 1/100
b = 97 - 100/100 = 96.
Naša enačba se zato glasi: f1(n) = 1/100*(n^2) + 96.
Sedaj lahko izračunamo čas pri n = 1000 preprosto z funkcijo f1(1000).
Dobimo torej f1(1000) = 1/100*(1000)^2 + 96 = 10.096, kar znaša, če pretvorimo v ure in minute natanko: 2h 48min 16s.
2. Imamo torej podano funkcijo f2(n) = a*n + b, kjer je b = 96.
Poleg tega imamo podano še f2(1000) = 1096. Izračunamo še konstanto a na sledeč način:
f2(n) = a*n + 96
Iz pogoja f2(1000) dobimo:
1096 = a*1000 + 96 ===> a = 1
Torej je naša funkcija enaka f2(n) = n + 96.
Sedaj pa samo še izračunamo presečišče teh dveh funkcij, če želimo dobiti kdaj katero uporabiti, torej f1(n) = 1/100*(n^2) + 96 in f2(n) = n + 96.
Izenačimo funkciji f1 = f2
1/100*n^2 + 96 = n + 96
1/100*n^2 = n
n^2 = 100*n
n(n-100) = 0.
Torej se funkciji zamenjata pri n = 0 in n = 100, kar iz našega primera sledi, da se splača uporabljati f2 torej funkcijo z časovno zahtevnostjo O(n) za n od 0 do 100 in drugače f1 za n večji od 100.

Osebna orodja