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(2log n) 20 handelingen nodig zijn. (log 20 / log 210000000)
Alleen ik heb geen idee waarop dat gebaseerd is. Kan iemand me helpen?
Mvgrob
22-6-2004
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
jadex
23-6-2004
#25754 - Logaritmen - Student hbo