En esta pregunta sobre el recuento de inversiones , encontré un documento que demuestra un límite inferior en la complejidad del espacio para todos los algoritmos de transmisión (exactos) . He afirmado que este límite se extiende a todos los algoritmos de tiempo lineal. Esto es un poco audaz ya que, en general, un algoritmo de tiempo lineal puede saltar a voluntad (acceso aleatorio) que un algoritmo de transmisión no puede; tiene que investigar los elementos en orden. Puedo realizar múltiples pases, pero solo constantemente muchos (para tiempo de ejecución lineal).
Por lo tanto mi pregunta:
¿Se puede expresar cada algoritmo de tiempo lineal como un algoritmo de transmisión con muchas pasadas constantemente?
El acceso aleatorio parece evitar que una construcción (simple) demuestre una respuesta positiva, pero tampoco he podido encontrar un contraejemplo.
Dependiendo del modelo de máquina, el acceso aleatorio puede incluso no ser un problema, en tiempo de ejecución. Me interesarían las respuestas para estos modelos:
- Máquina de Turing, entrada plana
- RAM, entrada como matriz
- RAM, entrada como lista vinculada
Respuestas:
Para que los algoritmos de transmisión sean significativos, tienen que trabajar con una cantidad de espacio de trabajo significativamente menor que la entrada en sí. Por ejemplo, si permite la misma cantidad de espacio de trabajo que la entrada, puede indicar trivialmente cualquier algoritmo como un "algoritmo de transmisión de un solo paso" que primero copia la entrada al espacio de trabajo en un solo paso y luego solo usa el trabajo espacio.
Creo que es típico restringir el espacio de trabajo a lo más polilogarítmico en el tamaño de entrada cuando se habla de algoritmos de transmisión. Bajo este supuesto, la selección mediana no tiene un algoritmo de transmisión de paso O (1) por el resultado de Munro y Paterson [MP80]: cualquier algoritmo de transmisión de paso P para la selección mediana en N elementos tiene que almacenar Ω ( N 1 / P ) elementos. Por otro lado, la selección mediana tiene un algoritmo determinista de tiempo lineal bien conocido [BFPRT73].
[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest y Robert E. Tarjan. Límites de tiempo para la selección. Journal of Computer and System Sciences , 7 (4): 448–461, agosto de 1973. DOI: 10.1016 / S0022-0000 (73) 80033-9
[MP80] J. Ian Munro y Mike S. Paterson. Selección y clasificación con almacenamiento limitado. Informática teórica , 12 (3): 315–323, noviembre de 1980. DOI: 10.1016 / 0304-3975 (80) 90061-4
fuente
En el modelo de transmisión solo se le permite almacenar datos extra constantes o polilogarítmicos mientras escanea a través de la entrada. Si considera un algoritmo de tiempo lineal
que sigue el paradigma de dividir y conquistar , necesita almacenar más información y / o debe escanear sus datos tantas veces como la profundidad de la recursión.
Un ejemplo es el algoritmo DC3 para construir la matriz de sufijos de un textoT (dado como matriz en el modelo RAM). Para construir una matriz de sufijos, agrupa los caracteres en trillizos, de modo que obtienes un texto con nuevos supercaracteres . Puede hacer esto con un desplazamiento de , que da como resultado tres textos nuevos T 1 , T 2 , T 3 . Curiosamente, puede calcular la matriz de sufijos si tiene la matriz de sufijos de T 1 ⋅ T 2 en tiempo lineal. Por lo tanto, el algoritmo necesita0 , 1 , 2 T1, T2, T3 T1⋅ T2
hora. Esta recursión se resuelve claramente en . No veo cómo esto se puede convertir en un algoritmo de transmisión.t ( n ) = O ( n )
Otro ejemplo bien conocido es el clásico algoritmo de selección de tiempo lineal .
fuente
En el extremo inferior del espectro, hay una respuesta en el libro de transmisión de Muthu . Mire el rompecabezas 3. El problema es que, dada una matriz de enteros, todos en el rango [ 1 , n - 1 ] , encuentre un entero duplicado. Existe una solución de tiempo lineal de acceso aleatorio con bits O ( log n ) (equivalentemente,norte [ 1 , n - 1 ] O ( logn ) O ( 1 ) ω ( registron )
fuente
Incluso en la definición más simple de "algoritmo de transmisión" (un algoritmo que, después de cada iteración incremental en la fuente, resulta en el conocimiento inmediato de la siguiente pieza incremental del resultado), puedo pensar en algunos algoritmos lineales que no comportarse de esa manera. Los algoritmos de hash son grandes; FNV-1a es lineal al número de bytes en la fuente, pero no conocemos ninguna parte del hash final hasta que se haya procesado la fuente completa.
RadixSort, también conocido como BucketSort, es O (N) (técnicamente O (NlogM) donde M es el valor máximo en los N elementos, que se considera pequeño), y debe ejecutarse en su totalidad para garantizar que cualquier elemento individual esté en su lugar final.
Para ser un algoritmo de "transmisión", en su forma más simple, un algoritmo debe tener las siguientes dos propiedades, ninguna de las cuales está expresamente limitada en el tiempo:
Por lo tanto, la clase principal de algoritmos que se transmiten es la de los algoritmos que realizan "proyecciones" (transformaciones incrementales de una entrada a salidas X> 0).
fuente