de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Dynamic Binary Search

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Mehlhorn, K. (1979). Dynamic Binary Search. SIAM Journal on Computing, 8, 175-198.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-AF76-5
Zusammenfassung
We consider search trees under time-varying access probabilities. Let $S = \{ B_1 , \cdots ,B_n \} $ and let $p_i^t $ be the number of accesses to object $B_i $ up to time $t$, $W^t = \sum {p_i^t } $. We introduce D-trees with the following properties.1) A search for $X = B_i $ at time $t$ takes time $O(\log W^t /p_i^t )$. This is nearly optimal.2) Update time after a search is at most proportional to search time, i.e. the overhead for administration is small.