De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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 An3 tijseenheden (met A een constante) en nu kost het An3/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



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2022 WisFaq - versie 3