The shuffling bufferReportar como inadecuado

The shuffling buffer - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 PRISME - Geometry, Algorithms and Robotics CRISAM - Inria Sophia Antipolis - Méditerranée

Abstract : The complexity of randomized incremental algorithms is analyzed with the assumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be mixed what contradicts with the on-line nature of the algorithm. We present the shuffling buffer technique to introduce sufficient randomness to guarantee an improvement on the worst case complexity by knowing only k data in advance. Typically, an algorithm with $On^2$ worst-case complexity and On or On log n randomized complexity has an On^2 log k-k complexity for the shuffling buffer. We illustrate this with binary search trees, the number of Delaunay triangles or the number of trapezoids in a trapezoidal map created during an incremental construction.

Autor: Olivier Devillers - Philippe Guigue -



Documentos relacionados