A probabilistic analysis of some tree algorithms

被引：10

作者：

Mohamed, H ^{[1
]}

Robert, P ^{[1
]}

机构：

[1] INRIA, F-78153 Le Chesnay, France

来源：

ANNALS OF APPLIED PROBABILITY | 2005年 / 15卷 / 04期

关键词：

splitting algorithms; divide and conquer algorithms; unusual laws of large numbers; asymptotic oscillating behavior; data structures; tries; renewal theorem;

D O I：

10.1214/105051605000000494

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

In this paper a general class of tree algorithms is analyzed. It is shown that, by using an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily without resorting to the usual complex analysis techniques. This approach gives a unified probabilistic treatment of these questions. It simplifies and extends some of the results known in this domain.

引用

页码：2445 / 2471

页数：27

共 27 条

[21] A probabilistic analysis of trie-based sorting of large collections of line segments in spatial databases
Lindenbaum, M
Samet, H
Hjaltason, GR
SIAM JOURNAL ON COMPUTING, 2005, 35 (01) : 22 - 58
[22] Execution time analysis of a top-down R-tree construction algorithm
Alborzi, Houman
Samet, Hanan
INFORMATION PROCESSING LETTERS, 2007, 101 (01) : 6 - 12
[23] Data structures and algorithms to support interactive spatial analysis using dynamic Voronoi diagrams
Gahegan, M.
Lee, I.
Computers, Environment and Urban Systems, 2000, 24 (06) : 509 - 537
[24] Experimental analysis of algorithms for updating minimum spanning trees on graphs subject to changes on edge weights
Ribeiro, Celso C.
Toso, Rodrigo F.
EXPERIMENTAL ALGORITHMS, PROCEEDINGS, 2007, 4525 : 393 - +
[25] Performance Analysis of Various Combination Sorting Algorithms for Large Dataset to fit to a Multi-Core Architecture
Suresh, Aparna
George, A. K.
PROCEEDINGS OF THE 2018 SECOND INTERNATIONAL CONFERENCE ON INVENTIVE COMMUNICATION AND COMPUTATIONAL TECHNOLOGIES (ICICCT), 2018, : 51 - 56
[26] Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems
Liu, Hongwei
Wang, Ting
Liu, Zexian
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2022, 83 (02) : 651 - 691
[27] An Efficient Backward/Forward Sweep Algorithm for Power Flow Analysis through a Novel Tree-Like Structure for Unbalanced Distribution Networks
Petridis, Stefanos
Blanas, Orestis
Rakopoulos, Dimitrios
Stergiopoulos, Fotis
Nikolopoulos, Nikos
Voutetakis, Spyros
ENERGIES, 2021, 14 (04)

← 1 2 3 →