WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Logaritme in een Binaire Search Tree

Er wordt beweerd dat er de algoritme O(log n) (Big-0 notation genoemd) wordt gebruikt om de tijd te berekenen voor hoelang het duurt om een bepaald aantal handelingen te voeren voor het vinden van een element in een BST.

Nu is er een voorbeeld gegeven dat in een BST waar 1000000 n-elementen voorkomen met de algoritme O(²log n) 20 handelingen nodig zijn. (log 20 / log 2 10000000)

Alleen ik heb geen idee waarop dat gebaseerd is. Kan iemand me helpen?

Mvg
rob
Student hbo - dinsdag 22 juni 2004

Antwoord

Het is gebaseerd op het gemiddeld aantal handelingen dat je moet doen om in een binair geordende boom (bv. van sofinummers van leerlingen die zich bij een school inschrijven) een record te vinden.
Het antwoord op je vraag kun je vinden bij een van de volgende links:

Binary search 1 (pdf)
Binary search 2
Binary search 3 (ppt)
Binary search 4 (pdf)

En zo kun je er zelf nog veeeeeeel meer vinden.

Met vriendelijke groet

JaDeX

Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 23 juni 2004