Ordenar usando pilas de solo lectura

14

Considere la siguiente configuración:

  • se nos da una pila que contiene elementos.snorte
  • podemos usar un número constante de pilas adicionales.O(1)
  • podemos aplicar las siguientes operaciones en estas pilas:
    1. comprobar si una pila está vacía
    2. compara los elementos principales de dos pilas,
    3. eliminar el elemento superior en una pila,
    4. imprime el elemento superior en una pila,
    5. copia el elemento superior de una pila en otra pila,
    6. copie el contenido de una pila a otra pila.

Tenga en cuenta que estas son las únicas operaciones permitidas. No podemos intercambiar elementos y no podemos insertar ningún elemento en ninguna de las pilas, con la excepción de copiar el elemento superior en una pila (después de lo cual se descarta el contenido anterior de la pila de destino y solo contendrá el elemento copiado) .

Aquí hay un algoritmo para ordenar las pilas con comparaciones:O(n2)

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

¿Podemos hacerlo mejor?

¿Existe un programa que imprima la lista ordenada de los elementos en las pilas usando solo comparaciones ?O(nlogn)

Siddharth
fuente
2
¿Parece que los registros se comportan como pilas? Parece que estás hablando de operaciones push y pop. ¿Esas son tus preguntas? ¿Cómo ordenarías una pila usando varias pilas y operaciones de pila?
AturSams
2
Con registros puede: simplemente ponga cada número en un registro ( O ( n ) ) y luego aplique un algoritmo de clasificación habitual ( O ( n lg n ) ). nO(n)O(nlgn)
Kaveh
1
¿Desea usar registros ? De lo contrario, el problema se trivializa, como comentó Kaveh. O(1)
Yuval Filmus
1
De nada. Pensé que se nos da una cantidad de pilas, no solo una, lo arreglaré.
Kaveh
2
@akappa, ¿estás seguro de que se puede usar en esta visión? No podemos mantener ninguna pérdida arbitraria de tamaño mayor que 1. ¿No necesita almacenar los bloques ordenados?
Kaveh

Respuestas:

1

Creo que ahora puedo demostrar un límite inferior no trivial. La idea es implementar cualquier programa de este tipo con una familia de programas de ramificación de comparación. La suposición de 'solo lectura' significa que nuestra familia de programas de ramificación usa poco espacio , es decir, . Luego aplicamos el límite inferior S T = Ω ( n 2 ) demostrado por Borodin et al. en "Una compensación espacio-tiempo para clasificar en máquinas no ajenas". Esto nos da un límite inferior n 2 / log n por el momento.O(logn)ST=Ω(n2)n2/logn

En un poco más de detalle: podemos prescindir de la operación 5 anterior. Hablando en términos generales, si ya podemos comparar los encabezados de dos listas e imprimir el encabezado de una lista, entonces no hay necesidad de aislar el encabezado de una lista en un registro particular. Asumiendo esto, vemos que cada registro en la máquina solo almacena una subcadena final de la entrada.

Supongamos que nuestro programa de registro tiene líneas de código y k registros, X 1 , ... , X k .kX1,,Xk

Fix . Construimos el programa de ramificación de comparación para cadenas de longitud n de la siguiente manera. Cree un nodo para cada tupla ( i , d 1 , ... , d k ) donde 1 i y 0 d 1 , ... , d kn . La idea es que los cálculos en la máquina de registro corresponden a rutas en el programa de ramificación, y estamos en el nodo ( i , d 1 , ... , dnn(i,d1,,dk)1i0d1,,dkn si estamos en la línea i en la máquina de registro y la longitud de la cadena almacenada en X i es d i . Ahora, tenemos que definir los bordes dirigidos del programa de ramificación(i,d1,,dk)iXyodi

Si la línea es de la formai

si entonces goto i 1 más goto i 2Xu<Xvi1i2

entonces, para todos los , el nodo ( i , d 1 , ... , d k ) se etiqueta comparando el elemento d u -th y d v -th de entrada, y haciendo que el borde "verdadero" vaya a ( i 1 , d 1 , ... , d k ) , y el borde "falso" a ( i 2 , d 1 , ... , d kd1,,dk(i,d1,,dk)dudv(i1,d1,,dk) .(i2,d1,,dk)

Si la línea es de la formai

, ir a la línea i X1tail(X2)i

entonces hay una flecha desde cualquier nodo a ( i ' , d 2 - 1 , ... , d k ) .(i,d1,,dk)(i,d21,,dk)

Si la línea es de la formai

, ir a la línea i print(head(Xu))i

entonces hay una flecha desde cualquier nodo a ( i ' , d 1 , ... , d k ) que está etiquetada por el nodo d u -ésimo de la entrada.(i,d1,,dk)(i,d1,,dk)du

Esperemos que estos ejemplos aclaren cómo tengo la intención de construir mi programa de ramificación. Cuando todo está dicho y hecho, este programa de ramificación tiene a lo sumo nodos, por lo que dispone de espacio O ( log n )nkO(logn)

Siddharth
fuente
0

¿Eres capaz de contar elementos? Entonces, creo, hay una implementación de Mergesort bastante fácil. Si pudieras poner símbolos adicionales en la pila, podrías resolverlo con 3 pilas como esta:

Si solo tenemos un elemento, la lista ya está ordenada. Ahora suponga que ya hemos ordenado la mitad superior de la pila. Podemos copiar la mitad superior (en orden inverso) a la segunda pila y colocar un símbolo de separación encima de ella. Ahora tenemos nuevamente 3 pilas (ya que podemos ignorar los símbolos ya ordenados debajo del símbolo de separación) y podemos ordenar la mitad inferior. Finalmente, podemos copiar la mitad inferior ordenada en una tercera pila en orden inverso y fusionar ambas mitades nuevamente en la pila original.

Todas las operaciones cuestan tiempo lineal, por lo tanto, hemos ordenado la lista en O(nlogn)

(Tenga en cuenta que necesitamos pilas de tamaño debido a los símbolos de separación, pero esto se puede corregir fácilmente usando otra pila)nlogn


Como no puede poner nuevos elementos en la pila, puede tener problemas en los puntos de separación. Para resolver esto, puede hacer lo siguiente con algunas pilas adicionales:

Copie los elementos superiores en una pila adicional, luego proceda con los elementos restantes como antes. Ahora sabe exactamente la cantidad de elementos que debe considerar en cada paso y, por lo tanto, no necesita ningún símbolo de separación.n2logn

Finalmente, repita el procedimiento con los elementos adicionales en la mayoría de las veces y fusione con la pila original en tiempo lineal. Clasificación de los costos de las pilas, para algunos c constantes , como máximo c n log n + c nlognctiempo, mientras que la fusión cuesta unOadicional(nlogn).cnlogn+cn2logn2+cn4logn4+ ...=O(nlogn)O(nlogn)

cero
fuente
No estoy seguro de entender. ¿Cómo podemos, por ejemplo, copiar la mitad superior de la pila en orden inverso en otra pila cuando nunca podemos empujar ningún elemento en ninguna pila?
Siddharth
No podemos empujar ningún elemento nuevo a una pila, pero de acuerdo con 5 podemos empujar el elemento superior de una pila a otra. Por lo tanto, copiar la pila en orden inverso requiere como máximo un tiempo lineal. Entonces, supongo, ¿eso no era lo que pedías?
cero
No puede empujar nada encima de otros elementos como se explica en la pregunta.
Kaveh