¿Árboles equilibrados simples con O (1) concat?

Respuestas:

5

Puede hacer trivialmente una estructura de datos con O (1) tiempo de concatenación amortizado , simplemente reinsertando todo de un árbol en el otro en la concatenación (que tiene un costo O (n log n), exactamente el mismo que se usó para construir ese árbol en En primer lugar, el tiempo total sigue siendo O (n log n)), pero esto es trampa.

Para el peor de los casos O (1), los autores afirman que fue un problema abierto para cualquier estructura de datos, por lo que no creo que encuentre una respuesta fácil.

Alexandre Passos
fuente
1
No estoy seguro si Brodal et al. significaba que era un problema abierto incluso en un entorno efímero. ¿Estás hablando de la oración en el resumen que hace referencia a "un problema abierto planteado por Kaplan y Tarjan"? Si es así, creo que está claro por el contexto de ese documento que K&T decía que la pregunta estaba abierta en una estructura puramente funcional.
jbapple
Descargué el documento, pero dice claramente que "Ellos [K&T] preguntaron si la operación de unión se puede implementar en O (1) peor de los casos, incluso en un entorno efímero, al tiempo que admite búsquedas y actualizaciones en tiempo logarítmico".
Blaisorblade
Buen punto, Blaisorblade. Perdí esa frase.
jbapple
nO(nlogn)O(nlog2n)
4

Descargué el documento que mencionas y responde "no", al menos en el momento de la publicación del documento. Eso es por dos razones:

  1. Se requiere un documento para revisar adecuadamente el trabajo relacionado, y lo hacen en la introducción, con un resumen en la Fig. 1, que dice "no". Al menos si se ha publicado en una conferencia de buena reputación, pero así es (Brodal es citado un par de veces en "Estructuras de datos puramente funcionales" por C. Okasaki, una referencia sobre el tema).

    Sin embargo, mencionan en el texto un algoritmo con tiempo de búsqueda O (log n log log n) y concatenación en tiempo O (1), bosquejado en el documento K&T de STOC '96. Puede ser interesante para ti.

    • El desafío abierto de K&T que resuelven es sobre diccionarios con concatenación O (1) y búsqueda / inserción / eliminación O (log N), incluso para estructuras efímeras.

El punto 1. también asegura que simplemente puede buscar documentos que citan este para encontrar resultados posteriores, tendrían que citarlo.

Si la pregunta tuviera relevancia práctica (pero no se supone que lo sea), creo que los factores constantes son más importantes que la diferencia entre O (1) y O (log N) (como se discutió en la Introducción a los algoritmos de Sedgewick), entonces solo debe buscar puntos de referencia para el caso de uso de su aplicación.

Blaisorblade
fuente
ESOP es una conferencia de buena reputación, si eso es lo que querías decir.
Charles Stewart
Esa fue mi pregunta, pero para ESA, donde se publica el artículo, no ESOP (tal vez lo quisiste decir). No estaba seguro de poder confiar en el rango de la conferencia. Esta página de clasificación no oficial sugiere que también la ESA tiene buena reputación: www3.ntu.edu.sg/home/assourav/crank.htm
Blaisorblade