¿Se conocen los resultados que descartan la existencia de estructuras de datos "demasiado buenas para ser verdaderas"?
Por ejemplo: ¿se puede agregar la funcionalidad y J o i n a una estructura de datos de mantenimiento de pedidos (ver Dietz y Sleator STOC '87 ) y aún obtener operaciones de tiempo O ( 1 ) ?
O: ¿se puede implementar un conjunto ordenado con teclas enteras y operaciones de tiempo ? Por supuesto, esto es al menos tan difícil como descubrir un algoritmo de tiempo lineal para ordenar enteros.
¿Se ha demostrado que la respuesta es no para cualquiera de estas preguntas? ¿Se conocen los resultados de límite inferior para cualquier estructura de datos naturales?
ds.data-structures
big-list
lower-bounds
time-complexity
Shaun Harker
fuente
fuente
Respuestas:
Vea el documento para más detalles. Algunos otros documentos de Mihai también son relevantes y agradables.
ACTUALIZACIÓN: descubrí que su tesis doctoral " Técnicas de límite inferior para estructuras de datos " proporciona límites inferiores para muchos problemas centrales de estructura de datos utilizando las técnicas que desarrolló. Ciertamente vale la pena leerlo.
fuente
La respuesta a cualquiera de sus preguntas depende del modelo de cálculo. Por ejemplo, en muchas máquinas, multiplicar enteros es más costoso que agregarlos. Algunos modelos reflejan esto, mientras que otros no.
Para una respuesta a su pregunta sobre conjuntos ordenados de enteros, Andersson y Thorup discuten una solución asintóticamente óptima para mantener un conjunto dinámico ordenado de enteros en el modelo RAM en el espacio polinomial en su documento "Conjuntos ordenados dinámicos con árboles de búsqueda exponencial" . El límite que logran esO ( logn / logIniciar sesiónnorte-----------√) . El documento que cita el límite inferior es "Límites óptimos para el problema del predecesor y problemas relacionados" de Beame y Fich .
fuente
En extensión a lo que menciona a su pregunta, un ejemplo clásico es el uso del hecho de que los enteros no se pueden ordenar usando comparaciones más rápido queO ( n logn ) para demostrar la inexistencia de superestructuras.
Además, no es inusual usar argumentos de teoría de la información (por ejemplo, la complejidad de Kolmogorov) para probar límites inferiores para las estructuras de datos.
fuente