ON TREE-GROWING SEARCH STRATEGIES
成果类型：
Article
署名作者：
Lent, Janice; Mahmoud, Hosam M.
署名单位：
George Washington University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
1996
页码：
1284-1302
关键词：
摘要：
Using the concept of a tree-growing'' search strategy, we prove that for most practical insertion sorting algorithms, the number of comparisons needed to sort n keys has asymptotically normal behavior. We prove and apply a sufficient condition for asymptotically normal behavior. The condition specifies a relationship between the variance of the number of comparisons and the rate of growth in height of the sequence of trees that the search strategy grows.''