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

woensdag 23 juni 2004

©2001-2024 WisFaq