Invertir una lista usando dos colas

12

Esta pregunta está inspirada en una pregunta existente sobre si una pila se puede simular usando dos colas en el tiempo amortizado por operación de pila. La respuesta parece ser desconocida. Aquí hay una pregunta más específica, correspondiente al caso especial en el que todas las operaciones PUSH se realizan primero, seguidas de todas las operaciones POP. ¿Cuán eficientemente se puede revertir una lista de elementos usando dos colas inicialmente vacías? Las operaciones legales son:NO(1)N

  1. Poner en cola el siguiente elemento de la lista de entrada (al final de cualquiera de las colas).
  2. Elimine el elemento en la cabecera de cualquiera de las colas y vuelva a colocarlo en cola (hasta la cola de cualquiera de las colas).
  3. Elimine el elemento en la cabecera de cualquiera de las colas y agréguelo a la lista de salida.

Si la lista de entrada consta de elementos , ¿cómo funciona el número mínimo de operaciones necesarias para generar la lista de salida invertida comportarse? Una prueba de que crece más rápido que O (N) sería especialmente interesante, ya que resolvería la pregunta original en forma negativa.[ N , N - 1 , . . . , 2 , 1 ] O ( N )[1,2,...,N1,N][N,N1,...,2,1]O(N)


Actualización (15 de enero de 2011): el problema se puede resolver en O(NlogN) , como se muestra en las respuestas enviadas y sus comentarios; y un límite inferior de Ω(N) es trivial. ¿Se puede mejorar cualquiera de estos límites?

mjqxxxx
fuente
Para aclarar: por "el último elemento de cualquiera de las colas", ¿se refiere al elemento que está al principio de la cola?
Peter Taylor
@ Peter: Sí, gracias por la aclaración. He editado la pregunta.
mjqxxxx
¿Son apiladas las listas de entrada y salida? Si es así, n op1s (a la misma cola) seguido de n op3s hace lo contrario, ¿verdad? Creo que me falta algo importante.
jbapple
@jbapple: No, no son pilas. Debe escribir elementos en la lista de salida en el orden opuesto al que se leyeron de la lista de entrada.
mjqxxxx

Respuestas:

11

Si N es una potencia de dos, creo que las operaciones O (N log N) son suficientes, incluso para un problema algo más restringido en el que todos los elementos comienzan en una de las colas y deben terminar en orden inverso en una de las colas (sin las listas de entrada y salida).

En los pasos O (N) es posible comenzar con todos los elementos en una cola, jugar "uno para usted uno para mí" para dividirlos en subconjuntos alternos en la otra cola, y luego concatenarlos de nuevo en una cola. En términos de las representaciones binarias de las posiciones de los elementos, esto implementa una operación de rotación.

En los pasos O (N) también es posible extraer pares de elementos de una cola, intercambiarlos y luego volverlos a colocar, invirtiendo todos los pares. En términos de las representaciones binarias de las posiciones de los elementos, esto complementa el bit de orden inferior de la posición.

Al repetir O (log N) multiplicado por un cambio aleatorio y un intercambio por pares, podemos complementar todos los bits de las representaciones binarias de las posiciones, que es lo mismo que invertir la lista.

David Eppstein
fuente
Luego, puede dividir la lista en una representación binaria e invertir pieza por pieza para un algoritmo O (n lg n), creo.
jbapple
Estaba pensando que uno podría extenderse a todo N usando un árbol 2-3 en lugar de binario, pero tal vez su idea sea más simple. Pero, ¿cómo invierte cada una de las piezas O (log n) en pasos totales O (n log n)?
David Eppstein
El tiempo es O (suma (2 ^ i) lg (2 ^ i)) para i de 0 a [lg n], que Wolfram alpha dice que es O (n lg n): wolframalpha.com/input/?i=sum+ (2 ^ k) + log2 + (2 ^ k) + de + 0 + a + log2 + n
jbapple
Claro, si puede invertir cada una de las piezas en tiempo proporcional a su longitud multiplicada por su registro, ya está. Pero debes colocar las piezas en algún lugar una vez que las hayas invertido, y eso podría hacer que sea más difícil invertir las piezas restantes.
David Eppstein el
El problema plantea una "lista de salida". ¿Podemos ponerlos allí?
jbapple
1

El mejor algoritmo que se me ocurre requiere transferencias de una cola a otra.i=0N/21(N2i2)

Permite nombrar dos colas disponibles como izquierda y derecha. Aquí está la idea básica de este algoritmo con la suposición de que N es par:

  1. Lea los valores de la lista inicial de elementos e inserte todos los números impares en la cola izquierda y los números pares en la cola derecha
  2. Uno de los primeros pasos, la forma más rápida de generar el valor máximo es transferir N / 2-1 elementos de la cola derecha a la izquierda y extraer el valor superior de la cola derecha a la lista de salida
  3. Ahora tenemos que hacer lo mismo para otra cola: transfiera N / 2-1 elementos de la cola izquierda a la derecha y saque el elemento superior de la cola izquierda a la lista de salida
  4. Intercambie colas y repita los pasos 2 y 3 para N = N-2

Es fácil ver cómo el algoritmo debería funcionar para N. impar

Elalfer
fuente
Puede usar $ ... $ para insertar el código LaTeX-ish (menos el \).
Mark Reitblatt