Problema de mantenimiento de pedidos
En informática , el problema de mantenimiento de órdenes implica mantener un conjunto totalmente ordenado que soporta las siguientes operaciones:
Paul Dietz introdujo por primera vez una estructura de datos para resolver este problema en 1982. [1] Esta estructura de datos admite insert(X, Y)en (en notación Big O ) tiempo amortizado y en tiempo constante, pero no admite eliminación. Athanasios Tsakalidis usó árboles BB [α] con los mismos límites de rendimiento que admiten la eliminación y un rendimiento mejorado de inserción y eliminación en el tiempo amortizado con indirección. [2] Dietz y Daniel Sleator publicaron una mejora al tiempo constante del peor de los casos en 1987. [3] Michael Bender, Richard Cole y Jack Zito publicaron alternativas significativamente simplificadas en 2004. [4]order(X, Y)Bender, Fineman, Gilbert, Kopelowitz y Montes también publicaron una solución desamortizada en 2017. [5]
Las estructuras de datos eficientes para el mantenimiento de pedidos tienen aplicaciones en muchas áreas, incluida la persistencia de la estructura de datos , [6] algoritmos de gráficos [7] [8] y estructuras de datos tolerantes a fallas. [9]
Un problema relacionado con el problema del mantenimiento del orden es el problema de etiquetado de listas en el que, en lugar de la order(X,
Y)operación, la solución debe mantener una asignación de etiquetas de un universo de números enteros a los elementos del conjunto de modo que X precede a Y en el orden total si y solo si a X se le asigna una etiqueta menor que Y. También debe admitir una operación que devuelva la etiqueta de cualquier nodo X. Tenga en cuenta que se puede implementar simplemente comparando ylabel(X)order(X, Y)label(X)label(Y)de modo que cualquier solución al problema de etiquetado de listas da inmediatamente a uno el problema de mantenimiento de pedidos. De hecho, la mayoría de las soluciones al problema de mantenimiento de pedidos son soluciones al problema de etiquetado de listas aumentadas con un nivel de direccionamiento indirecto de la estructura de datos para mejorar el rendimiento. Veremos un ejemplo de esto a continuación.
Por razones de eficiencia, es deseable que el tamaño del universo esté limitado por el número de elementos almacenados en la estructura de datos. En el caso de que se requiera ser lineal, el problema se conoce como mantenimiento de matriz empaquetada o problema de mantenimiento de archivo secuencial denso . Considere los elementos como entradas en un archivo y las etiquetas como las direcciones donde se almacena cada elemento. Entonces, una solución eficiente al problema de mantenimiento de la matriz empaquetada permitiría inserciones y eliminaciones eficientes de entradas en el medio de un archivo sin sobrecarga de espacio asintótico. [10] [11] [12] [13] [14] Este uso tiene aplicaciones recientes en estructuras de datos ajenas a la memoria caché[15] y clasificación in situ óptima en el peor de los casos. [dieciséis]
Sin embargo, bajo algunas restricciones, se han encontrado límites inferiores en el desempeño de inserción en soluciones del problema de etiquetado de listas con universos lineales [17] mientras que veremos más adelante que una solución con un universo polinomial puede realizar inserciones en el tiempo.
