Izpitno vprašanje RAČ2PRA 4000

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 08:52, 26 april 2007
METARAM (Pogovor | prispevki)
Vprašanje
← Prejšnja različica
Različica od 08:52, 26 april 2007
METARAM (Pogovor | prispevki)
Vprašanje
Naslednja različica →
Vrstica 3: Vrstica 3:
Imamo program, katerega čas izvajanja je O(n<sup>2</sup>), 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. Imamo program, katerega čas izvajanja je O(n<sup>2</sup>), 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? 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. 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. Program smo pognali pri n = 1000 in je delo opravil v 1096 sekundah.

Različica od 08:52, 26 april 2007

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