WisFaq!

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
25-8-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
29-8-2010