Classificação usando pilhas somente leitura

Considere a seguinte configuração:

• nos é dada uma pilha $s$ que contém $n$ itens.
• podemos usar um número constante $O(1)$de pilhas extras.
• podemos aplicar as seguintes operações nessas pilhas:
  1. verifique se uma pilha está vazia,
  2. compare os itens principais de duas pilhas,
  3. exclua o item superior em uma pilha,
  4. imprima o item superior em uma pilha,
  5. copie o item superior de uma pilha para outra pilha,
  6. copie o conteúdo de uma pilha para outra pilha.

Observe que essas são as únicas operações permitidas. Não podemos trocar itens e não temos permissão para enviar nenhum item para nenhuma das pilhas, com exceção de copiar o item superior em uma pilha (após o qual o conteúdo anterior da pilha de destino é descartado e conterá apenas o item copiado) .

Aqui está um algoritmo para classificar as pilhas com comparações de :$O(n^2)$

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 fazer melhor?

Existe um programa que imprima a lista classificada dos itens nas pilhas usando apenas comparações ?$O(n\log n)$

Acho que agora posso demonstrar um limite inferior não trivial. A idéia é implementar qualquer programa com uma família de programas de comparação de ramificações. A suposição `` somente leitura '' significa que nossa família de programas de ramificação usa pouco espaço, isto é, . Em seguida, aplicamos o limite inferior S T = Ω ( n 2 ) comprovado por Borodin et al. em "Uma troca de tempo e espaço para classificação em máquinas não esquecidas". Isso nos dá um limite inferior de n 2 / log n para o tempo.$O(\log n)$$ST=\Omega(n^2)$$n^2/\log n$

Um pouco mais detalhadamente: podemos dispensar a operação 5 acima. Em termos gerais, se já podemos comparar os cabeçalhos de duas listas e imprimir o cabeçalho de uma lista, não há necessidade de isolar o cabeçalho de uma lista em um registro específico. Supondo isso, vemos que todo registro na máquina apenas armazena uma substring final da entrada.

Suponha que nosso programa de registro tenha linhas de código ek registradores, X 1 , … , X k .$\ell$$k$$X_1,\dots,X_k$

Fix . Construímos o programa de ramificação de comparação para cadeias de comprimento n da seguinte maneira. Crie um nó para cada tupla ( i , d 1 , … , d k ) em que 1 ≤ i ≤ ℓ e 0 ≤ d 1 , … , d k ≤ n . A idéia é que os cálculos na máquina de registro correspondam aos caminhos no programa de ramificação, e estamos no nó ( i , d 1 , … , $n$$n$$(i,d_1,\dots,d_k)$$1\le i\le \ell$$0\le d_1 ,\dots, d_k \le n$ se estamos na linha i na máquina registradora e o comprimento da string armazenada em X i é d i . Agora, temos que definir as arestas direcionadas do programa de ramificação$(i,d_1 ,\dots, d_k)$$i$$X_i$$d_i$

Se a linha tiver a forma$i$

Se Then GoTo i 1 pessoa Goto i $X_u<X_v$$i_1$$i_2$

então, para todo o nó ( i , d 1 , … , d k ) é rotulado comparando-se o elemento d u -th e d v -th da entrada e fazendo com que a borda "true" vá para ( i 1 , d 1 , $d_1,\dots,d_k$$(i,d_1,\dots,d_k)$$d_u$$d_v$ e a aresta "falsa" para ( i 2 , d 1 , … , d $(i_1,d_1,\dots,d_k)$ .$(i_2,d_1,\dots,d_k)$

$i$

$X_1 \leftarrow tail(X_2)$$i'$

existe uma seta de qualquer nó para $(i,d_1,\dots,d_k)$$(i',d_2-1,\dots,d_k)$

$i$

$print(head(X_u))$$i'$

$(i,d_1,\dots,d_k)$$(i',d_1,\dots,d_k)$$d_u$

$\ell\cdot n^k$$O(\log n)$

Você é capaz de contar elementos? Acho que existe uma implementação bastante fácil do Mergesort. Se você pudesse colocar símbolos adicionais na pilha, poderia resolvê-lo com 3 pilhas como esta:

Se tivermos apenas um elemento, a lista já estará classificada. Agora suponha que já classificamos a metade superior da pilha. Podemos copiar a metade superior (em ordem inversa) para a segunda pilha e colocar um símbolo de separação em cima dela. Agora, temos novamente 3 pilhas (já que podemos ignorar os símbolos já classificados abaixo do símbolo de separação) e podemos classificar a metade inferior. Finalmente, podemos copiar a metade inferior classificada para uma terceira pilha na ordem inversa e mesclar as duas metades de volta à pilha original.

Todas as operações custam tempo linear, portanto, classificamos a lista em $O(n \log n)$

$n \log n$

Como você não pode colocar novos elementos na pilha, pode haver problemas nos pontos de separação. Para resolver isso, você pode fazer o seguinte com algumas pilhas adicionais:

$n-2^{\lfloor \log n\rfloor}$

$\log n$$c$$cn \log n+c\frac{n}{2} \log \frac{n}{2}+c\frac{n}{4} \log \frac{n}{4}+\ ... = O(n \log n)$$O(n \log n)$