En un artículo clásico, Munro y Paterson estudian el problema de cuánto almacenamiento se requiere para que un algoritmo encuentre la mediana en una matriz ordenada aleatoriamente. En particular, se centran en el siguiente modelo:
la entrada se lee de izquierda a derecha varias veces P.
Se muestra que celdas de memoria son suficientes, pero el límite inferior correspondiente solo se conoce para P = 1. No he visto ningún resultado para P> 1. ¿Alguien sabe de tales límites inferiores?
Tenga en cuenta que la principal dificultad aquí es que en la segunda pasada la entrada ya no se ordena al azar.
ds.algorithms
space-bounded
data-streams
MassimoLauria
fuente
fuente
El primer documento en probar límites para más de 1 pase fue mi documento con Jayram y Amit de SODA'08. Luego está el documento que mencionó Warren, que mejora los límites mediante una prueba más limpia.
En resumen, entendemos la dependencia si permite constantes frente al número de pases. Por supuesto, estas constantes están en el exponente, por lo que puede solicitar una comprensión precisa. Mi queja principal es que el modelo de transmisión multipass no está tan bien motivado.
La pregunta más intrigante es si podemos probar un límite inferior del programa de ramificación. ¿Puede ser que incluso para un algoritmo de espacio acotado que puede acceder a la memoria como le plazca, la mejor estrategia es simplemente hacer streaming multipass?
La respuesta parece ser afirmativa, y tenemos un progreso parcial para demostrarlo.
fuente