WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Tijdscomplexiteit

Ik zit met een vraagje over informatica.

Een algoritme heeft een tijdscomplexiteit van O(n^3). Stel dat we een nieuwe computer aankopen die 10-maal zo snel is als onze huidige computer. Een hoeveel groter probleem (probleemgrootte n) kunnen we nu oplossen met hetzelfde algoritme binnen dezelfde rekentijd?

Hoe moet ik dit beredeneren?

Sander
Sander
Student universiteit - woensdag 25 augustus 2010

Antwoord

Op de oude machine kost het ongeveer A·n³ tijseenheden (met A een constante) en nu kost het A·n³/10 tijdseenheden. Om weer op de oude tijdsbesteding uit te komen moet je n met de derdemachtswortel van 10 (en dat is ongeveer 2.15) vermenigvuldigen; je kunt dus in dezelfde tijd ongeveer twee keer zoveel werk doen.

kphart

Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 29 augustus 2010