|
|||||
|
|
On Time-Space Efficiency of Digital Trees with Adaptive Multidigit Branching |
|
| Authors: | Yu. A. Reznik |
| Affiliation: | (1) RealNetworks, Inc., Seattle, WA, USA |
| Abstract: | Parameters of time-space efficiency and sparseness of nodes in trees with adaptive multidigit branching are studied. Both precise and asymptotic expressions, describing average behavior of these parameters in a memoryless model, are obtained. These expressions are used to establish a relation between parameters. As a result, conditions of time-space optimality of trees constructed with the use of Nilsson and Tikkanen algorithm are obtained. |
| Keywords: | digital search digital trees with adaptive branching LC-trees analysis of expected behavior of algorithms Bernoulli model asymptotic analysis Rice integral saddle-point method Van-der-Waerden conversion |
| 本文献已被 SpringerLink 等数据库收录！ | |