fundo
Vários anos atrás, quando eu era graduado, recebíamos uma lição de casa sobre análise amortizada. Não consegui resolver um dos problemas. Eu havia perguntado isso em teoria , mas nenhum resultado satisfatório foi encontrado. Lembro que o curso da TA insistiu em algo que ele não podia provar e disse que esqueceu a prova, e ... [você sabe o que].
Hoje me lembrei do problema. Eu ainda estava ansioso para saber, então aqui está ...
A questão
É possível implementar uma pilha usando duas filas , para que as operações PUSH e POP sejam executadas no tempo amortizado O (1) ? Se sim, você poderia me dizer como?
Nota: A situação é bastante fácil se queremos implementar uma fila com duas pilhas (com as operações correspondentes ENQUEUE & DEQUEUE ). Por favor, observe a diferença.
PS: O problema acima não é o dever de casa em si. A lição de casa não exigia limites inferiores; apenas uma implementação e a análise do tempo de execução.
Respostas:
Não tenho uma resposta real, mas aqui estão algumas evidências de que o problema está aberto:
Não é mencionado em Ming Li, Luc Longpré e Paul MB Vitányi, "O poder da fila", Structures 1986, que considera várias outras simulações intimamente relacionadas
Não é mencionado em Martin Hühne, "Sobre o poder de várias filas", Theor. Comp. Sci. 1993, um artigo subsequente.
Não é mencionado em Holger Petersen, "Stacks versus Deques", COCOON 2001.
Burton Rosenberg, "Rápido reconhecimento não determinístico de linguagens sem contexto usando duas filas", Inform. Proc. Lett. 1998, fornece um algoritmo O (n log n) de duas filas para reconhecer qualquer CFL usando duas filas. Mas um autômato de empuxo não determinístico pode reconhecer CFLs em tempo linear. Portanto, se houvesse uma simulação de uma pilha com duas filas mais rápidas que O (log n) por operação, Rosenberg e seus árbitros deveriam saber disso.
fonte
A resposta abaixo é 'trapaça', pois, embora não use espaço entre operações, as próprias operações podem usar mais que espaço. Veja em outro lugar neste tópico uma resposta que não tenha esse problema.O(1)
Embora eu não tenha uma resposta para sua pergunta exata, encontrei um algoritmo que funciona em tempo em vez deO(n). Eu acredito que isso é apertado, embora eu não tenha uma prova. De qualquer forma, o algoritmo mostra que tentar provar um limite inferior deO(n)é inútil, portanto, pode ajudar a responder sua pergunta.O(n−−√) O(n) O(n)
Apresento dois algoritmos, o primeiro sendo um algoritmo simples com um tempo de execução de para Pop e o segundo com um O ( √O(n) tempo de execução do Pop. Descrevo o primeiro, principalmente por sua simplicidade, para facilitar o entendimento do segundo.O(n−−√)
Para dar mais detalhes: o primeiro não usa espaço adicional, possui um Push pior caso (e amortizado) e O ( n ) O pior caso (e amortizado), mas o comportamento do pior caso nem sempre é acionado. Como não usa espaço adicional além das duas filas, é um pouco "melhor" do que a solução oferecida por Ross Snider.O(1) O(n)
O segundo usa um único campo inteiro (portanto, espaço extra), possui O ( 1 ) pior caso (e amortizado) Push e O ( √O(1) O(1) Pop amortizado. Portanto, o tempo de execução é significativamente melhor do que o da abordagem "simples", mas usa algum espaço extra.O(n−−√)
O primeiro algoritmo
Temos duas filas: fila de e fila s e c o n d . f i r s t será a 'fila push', enquanto s e c o n d será a fila já na 'ordem pilha'.first second first second
Código C # para o primeiro algoritmo
Isso pode ser bem legível, mesmo que você nunca tenha visto C # antes. Se você não souber o que são genéricos, substitua todas as instâncias de 'T' por 'string' em sua mente, por uma pilha de strings.
Análise
Obviamente, o Push funciona no tempo . Pop pode tocar tudo dentro f i r s t e s e c o n d uma quantidade constante de tempos, de modo que temos S ( n ) no pior dos casos. O algoritmo exibe esse comportamento (por exemplo) se alguém colocar n elementos na pilha e executar repetidamente uma única operação Push e uma única operação Pop em sucessão.O ( 1 ) fi r s t s e c o n d O ( n ) n
O segundo algoritmo
Temos duas filas: fila de e fila s e c o n d . f i r s t será a 'fila push', enquanto s e c o n d será a fila já na 'ordem pilha'.fi r s t s e c o n d fi r s t s e c o n d
Esta é uma versão adaptada do primeiro algoritmo, em que não faça imediatamente 'baralhamento' o conteúdo de a s e c o n d . Em vez disso, se f i r s t contém um número suficientemente pequeno de elementos em comparação com s e c o n d (ou seja, a raiz quadrada do número de elementos em s e c o n d ), apenas reorganizamos f i r s t em ordem de pilha e não a mescle comfi r s t s e c o n d fi r s t s e c o n d s e c o n d fi r s t .s e c o n d
Código C # para o primeiro algoritmo
Isso pode ser bem legível, mesmo que você nunca tenha visto C # antes. Se você não souber o que são genéricos, substitua todas as instâncias de 'T' por 'string' em sua mente, por uma pilha de strings.
Análise
Obviamente, o Push funciona no tempo .O ( 1 )
O pop trabalha em tempo amortizado. Existem dois casos: se| first| < √O ( n--√) , então embaralhamosfirstna ordem da pilha emO(|first|)=O(√| first|<|second|−−−−−−−√ first tempo. Se| first| ≥ √O(|first|)=O(n−−√) , então devemos ter pelo menos√|first|≥|second|−−−−−−−√ pede Push. Portanto, podemos apenas atingir esse caso a cada √n−−√ chama para Push e Pop. O tempo de execução real para este caso éO(n), portanto, o tempo amortizado éO( n)n−−√ O(n) .O(nn√)=O(n−−√)
Nota final
É possível eliminar a variável extra ao custo de tornar Pop um operação, por ter Pop reorganizarfirstem cada chamada, em vez de ter push fazer todo o trabalho.O(n−−√) first
fonte
Após alguns comentários na minha resposta anterior, ficou claro para mim que eu estava mais ou menos trapaceando: usei espaço extra ( espaço extra no segundo algoritmo) durante a execução do meu método Pop.O(n−−√)
O algoritmo a seguir não usa espaço adicional entre os métodos e apenas espaço extra durante a execução de Push e Pop. Push tem um O ( √O(1) amortizado tempo de execução e Pop tem umó(1)pior caso (e amortizado) tempo de funcionamento.O(n−−√) O(1)
Nota aos moderadores: não tenho certeza se minha decisão de fazer uma resposta separada é a correta. Eu pensei que não deveria excluir minha resposta original, pois ainda pode ter alguma relevância para a pergunta.
O algoritmo
Temos duas filas: fila de e fila s e c o n d . f i r s t será a 'cache', enquanto s e c o n d será o nosso principal 'depósito'. As duas filas sempre estarão em 'ordem de pilha'. f i r s t conterá os elementos na parte superior da pilha e s e c o n d irá conter os elementos na parte inferior da pilha. O tamanho de f i rfirst second first second first second sempre será, no máximo, a raiz quadrada de s e c o n d .first second
Código C # para o primeiro algoritmo
Esse código deve ser bem legível, mesmo se você nunca viu C # antes. Se você não souber o que são genéricos, substitua todas as instâncias de 'T' por 'string' em sua mente, por uma pilha de strings.
Análise
Obviamente, o Pop funciona no tempo no pior caso.O(1)
Push trabalha em tempo amortizado. Existem dois casos: se| first| < √O(n−−√) então Push levaO(√|first|<|second|−−−−−−−√ tempo. Se| first| ≥ √O(n−−√) então Push levaO(n)tempo, mas após esta operação,firstestará vazio. Vai levarO(√|first|≥|second|−−−−−−−√ O(n) first tempo antes de retomarmos este caso, portanto o tempo amortizado éO( nO(n−−√) tempo.O(nn√)=O(n−−√)
fonte
first.Enqueue(first.Dequeue())
. Você digitou algo errado?Eu afirmo que temos custo amortizado por operação. O algoritmo de Alex fornece o limite superior. Para provar o limite inferior, dou a pior sequência de movimentos PUSH e POP.Θ(N−−√)
A pior sequência de casos consiste em operações PUSH, seguidas por √N PUSH operações e √N−−√ operações POP, seguidas novamente por √N−−√ PUSH operações e √N−−√ operações POP, etc. Ou seja:N−−√
Considere a situação após as operações iniciais de PUSH. Não importa como o algoritmo funcione, pelo menos uma das filas deve ter pelo menos N / 2 entradas.N N/2
Agora considere a tarefa de lidar com o (primeiro conjunto de) Operações PUSH e POP. Qualquer tática algorítmica de qualquer natureza deve se enquadrar em um dos dois casos:N−−√
No primeiro caso, o algoritmo usará as duas filas. A maior dessas filas possui pelo menos entradas, portanto, devemos incorrer em um custo de pelo menos operações de fila N / 2 para recuperar eventualmente até mesmo um único elemento que ENQUADRAMOS e, posteriormente, DESIGAMOS desta fila maior.N/2 N/2
No segundo caso, o algoritmo não usa as duas filas. Isso reduz o problema de simular uma pilha com uma única fila. Mesmo que essa fila esteja inicialmente vazia, não podemos fazer melhor do que usá-la como uma lista circular com acesso seqüencial, e parece claro que devemos usar pelo menos Operações de fila N /2em média para cada um dos2 √N−−√/2 operações de pilha.2N−−√
Nos dois casos, é necessário pelo menos (operações em fila) para lidar com 2 √N/2 operações de pilha. Porque podemos repetir esse processo √2N−−√ vezes, precisamosN √N−−√ tempo para processar3operações de pilhaNno total, dando um limite inferior deΩ( √NN−−√/2 3N tempo amortizado por operação.Ω(N−−√)
fonte
Até onde eu sei, essa é uma ideia nova ...
fonte
Sem usar espaço extra, talvez usando uma fila priorizada e forçando cada novo push a dar uma prioridade maior que a anterior? Ainda não seria O (1).
fonte
Não consigo que as filas implementem uma pilha em tempo constante amortizado. No entanto, posso pensar em uma maneira de obter duas filas para implementar uma pilha no pior dos casos, no tempo linear.
Obviamente, podemos adicionar outro estado externo que nos diz se a última operação foi um push ou um pop. Podemos atrasar a movimentação de tudo de uma fila para outra até obtermos duas operações de envio consecutivas. Isso também torna a operação pop um pouco mais complicada. Isso nos dá O (1) complexidade amortizada para a operação pop. Infelizmente, o push permanece linear.
Tudo isso funciona porque cada vez que uma operação de envio é realizada, o novo elemento é colocado no início de uma fila vazia e a fila completa é adicionada ao final da mesma, revertendo efetivamente os elementos.
Se você deseja obter operações de tempo constante amortizadas, provavelmente precisará fazer algo mais inteligente.
fonte
Existe uma solução trivial, se sua fila permitir o carregamento antecipado, que exige apenas uma fila (ou, mais especificamente, deque). Talvez esse seja o tipo de fila que o curso TA na pergunta original tinha em mente?
Sem permitir o carregamento frontal, aqui está outra solução:
Esse algoritmo requer duas filas e dois ponteiros, que serão denominados Q1, Q2, primário e secundário, respectivamente. Após a inicialização, Q1 e Q2 estão vazios, pontos primários para Q1 e pontos secundários para Q2.
A operação PUSH é trivial, consiste apenas em:
A operação POP é um pouco mais envolvida; requer colocar em spool tudo, exceto o último item da fila principal, na fila secundária, trocar os ponteiros e retornar o último item restante da fila original:
Nenhuma verificação de limites é feita e não é O (1).
Enquanto digito isso, vejo que isso pode ser feito com uma única fila usando um loop for no lugar de um loop while, como Alex fez. De qualquer forma, a operação PUSH é O (1) e a operação POP se torna O (n).
Aqui está outra solução usando duas filas e um ponteiro, chamados Q1, Q2 e queue_p, respectivamente:
Na inicialização, Q1 e Q2 estão vazios e queue_p aponta para Q1.
Novamente, a operação PUSH é trivial, mas requer uma etapa adicional de apontar queue_p para a outra fila:
A operação da operação POP é semelhante a antes, mas agora há n / 2 itens que precisam ser rotacionados pela fila:
A operação PUSH ainda é O (1), mas agora a operação POP é O (n / 2).
Pessoalmente, para esse problema, prefiro a ideia de implementar uma fila única (deque) dupla e chamá-la de pilha quando quisermos.
fonte
fonte
Uma pilha pode ser implementada usando duas filas, usando a segunda fila como referência. Quando os itens são empurrados para a pilha, eles são adicionados ao final da fila. Cada vez que um item é populado, os elementos n-1 da primeira fila devem ser movidos para o segundo, enquanto o item restante é retornado. classe pública QueueStack implementa ts IStack {private IQueue q1 = new Queue (); private IQueue q2 = nova Fila (); push de vazio público (E e) {q1.enqueue (e) // O (1)} público E pop (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); retornar q2.dequeue (); } pivate void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}
fonte