Invertendo uma lista usando duas filas

12

Essa pergunta é inspirada em uma pergunta existente sobre se uma pilha pode ser simulada usando duas filas no tempo amortizado por operação da pilha. A resposta parece ser desconhecida. Aqui está uma pergunta mais específica, correspondente ao caso especial em que todas as operações PUSH são executadas primeiro, seguidas por todas as operações POP. Com que eficiência uma lista de elementos pode ser revertida usando duas filas inicialmente vazias? As operações legais são:NO(1)N

  1. Enfileire o próximo elemento da lista de entrada (até o final de qualquer fila).
  2. Enfileire o elemento na cabeça de qualquer fila e enfileire-o novamente (na cauda de qualquer fila).
  3. Retire da fila o elemento no início de qualquer fila e adicione-o à lista de saída.

Se a lista de entrada consistir em elementos , como o número mínimo de operações necessárias para gerar a lista de saída reversa se comportar? Uma prova de que cresce mais rápido que seria especialmente interessante, pois resolveria a questão original de forma negativa.[ N , N - 1 , . . . , 2 , 1 ] O ( N )[1,2,...,N1,N][N,N1,...,2,1]O(N)


Atualização (15 de janeiro de 2011): O problema pode ser resolvido em , conforme mostrado nas respostas enviadas e em seus comentários; e um limite inferior de é trivial. Qualquer um desses limites pode ser aprimorado?Ω ( N )O(NlogN)Ω(N)

mjqxxxx
fonte
Para esclarecer: por "o último elemento de qualquer fila" você está se referindo ao elemento no início da fila?
Peter Taylor
@ Peter: Sim, obrigado pelo esclarecimento. Eu editei a pergunta.
precisa saber é o seguinte
As listas de entrada e saída são pilhas? Nesse caso, n op1s (para a mesma fila) seguido por n op3s faz o inverso, certo? Eu acho que devo estar perdendo algo importante.
jbapple
@jbapple: Não, eles não são pilhas. Você precisa escrever elementos na lista de saída na ordem oposta em que foram lidos na lista de entrada.
precisa saber é o seguinte

Respostas:

11

Se N for uma potência de dois, acredito que as operações O (N log N) são suficientes, mesmo para um problema um pouco mais restrito, no qual todos os itens iniciam em uma das filas e devem terminar na ordem inversa em uma das filas (sem as listas de entrada e saída).

Nas etapas O (N), é possível começar com todos os elementos em uma fila, tocar "um para você um para mim" para dividi-los em subconjuntos alternados na outra fila e concatená-los novamente em uma fila. Em termos das representações binárias das posições dos itens, isso implementa uma operação de rotação.

Nas etapas O (N), também é possível extrair pares de elementos de uma fila, trocá-los e recolocá-los, revertendo todos os pares. Em termos das representações binárias das posições dos itens, isso complementa o bit de baixa ordem da posição.

Repetindo O (log N) vezes uma troca aleatória e uma troca pareada, podemos complementar todos os bits das representações binárias das posições - o que é o mesmo que reverter a lista.

David Eppstein
fonte
Então você pode dividir a lista em uma representação binária e reverter peça por peça para um algoritmo O (n lg n), eu acho.
jbapple
Eu estava pensando que alguém poderia estender a todos os N usando uma árvore 2-3 em vez de binária, mas talvez sua ideia seja mais simples. Mas como você reverte cada uma das partes de O (log n) nas etapas totais de O (n log n)?
David Eppstein
O tempo é O (soma (2 ^ i) lg (2 ^ i)) para i de 0 a [lg n], que o Wolfram alpha diz ser O (n lg n): wolframalpha.com/input/?i=sum+ (2 ^ k) + log2 + (2 ^ k) + de + 0 + a + log2 + n
jbapple
Claro, se você pode reverter cada uma das peças no tempo proporcionalmente ao comprimento vezes o log, está pronto. Mas você deve colocar as peças em algum lugar depois de revertê-las, e isso pode dificultar a reversão das peças restantes.
David Eppstein
O problema postula uma "lista de saída". Podemos colocá-los lá?
jbapple
1

O melhor algoritmo em que posso pensar exige transferências de uma fila para outra.i=0N/21(N2i2)

Vamos nomear duas filas disponíveis como esquerda e direita. Aqui está a idéia básica desse algoritmo com a suposição de que N é par:

  1. Leia os valores da lista inicial de elementos e envie todos os números ímpares para a fila da esquerda e os números pares para a fila da direita
  2. Em um primeiro passo, a maneira mais rápida de gerar o valor máximo é transferir elementos N / 2-1 da fila da direita para a esquerda e exibir o valor superior da fila da direita na lista de saída
  3. Agora temos que fazer o mesmo para outra fila - transferir elementos N / 2-1 da fila esquerda para a direita e colocar o elemento superior da fila esquerda na lista de saída
  4. Troque filas e repita as etapas 2 e 3 para N = N-2

É fácil ver como o algoritmo deve funcionar para N. ímpar

Elalfer
fonte
Você pode usar $ ... $ para inserir o código LaTeX-ish (menos o \).
Re