O que se sabe sobre estruturas de dados que podem manter uma sequência de itens sujeitos às duas operações a seguir?
- Pressione (x): adicione x ao final da sequência e retorne um identificador para sua posição na sequência
- Extrair (S): dado um conjunto não ordenado de identificadores, remova os itens nessas posições da sequência e retorne uma lista dos itens removidos em ordem de sequência
Se desejar, você pode pensar nisso como uma pilha ou fila com uma operação de divisão que o divide em duas pilhas: a operação de extração pode ser usada para implementar uma operação de pop ou desenfileiramento, e a sequência extraída de itens também pode ser colocada de volta para uma pilha ou fila diferente.
O que eu já sei: é possível manter a sequência como uma lista duplamente vinculada, onde cada identificador é apenas um ponteiro para um nó da lista vinculada, e cada nó também armazena um número de posição que permite comparações rápidas entre as posições de dois elementos não relacionados na sequência. Não é difícil atualizar os números de posição à medida que a estrutura de dados progride, para que todos sejam números inteiros positivos com o valor máximo , onde é o número atual de itens na lista. Com essa estrutura de dados, a única parte difícil de uma operação de extração é classificar os itens extraídos pelos números de posição. Uma extração de itens levan k O ( k √ tempo aleatório esperado usando o algoritmo de classificação inteira de Han e Thorup do FOCS 2002, por exemplo, e uma operação push leva tempo constante.
O que eu não sei: é possível lidar com extração no tempo e empurrar no tempo constante? Existe literatura sobre esse problema? É tão difícil quanto a classificação inteira?
Motivação: esta é a etapa básica necessária para solicitar os itens no algoritmo de programação Coffman-Graham, que também possui aplicações no desenho de gráficos. A parte difícil de Coffman-Graham é uma ordem topológica lexicográfica. Isso pode ser feito mantendo, para cada indegree diferente, uma sequência dos vértices com aquele indegree no subgráfico induzido pelos vértices restantes. Em seguida, remova repetidamente o primeiro vértice da sequência de vértices com zero nulo e adicione-o à ordem topológica; extraia os vizinhos de dos graus aos quais pertenciam anteriormente e empurre-os para a sequência pelo próximo grau menor. Então umv O ( k ) o tempo para as operações de extração nessa estrutura de dados levaria a uma implementação linear em tempo do algoritmo de Coffman-Graham.
Desde que originalmente perguntei isso, encontrei um artigo de Sethi de 1976 que permite que o algoritmo Coffman – Graham seja implementado em tempo linear e o inclua no meu artigo da Wikipedia sobre o algoritmo Coffman – Graham , de modo que a motivação original é menos significativa. Ainda estou curioso para saber qual é a resposta.
fonte
Respostas:
Eu acho que isso é pelo menos tão difícil quanto classificar um conjunto de números inteiros com "conselhos aleatórios" do tamanho polinomial em n . Por conselho aleatório, quero dizer que para qualquer n existe uma distribuição fixa D n (dependendo apenas de n ) sobre cadeias de tamanho poli ( n ) e nosso algoritmo (modelado por uma máquina RAM) recebe acesso aleatório a uma única amostra de D n . D n é a estrutura de dados (randomizada) depois de pressionar [ n ]S⊆[n] n n Dn n n Dn Dn [n] O(1)
Portanto, a mensagem é que, a menos que algumas informações secundárias "livres", que dependem apenas do limite superior dos números inteiros, possam facilitar a classificação por números inteiros, a extração é tão difícil quanto a classificação por números inteiros.
Isso implica uma relação entre os dois problemas sem o modelo estranho? Essa noção de conselho aleatório é algo conhecido? É como um protocolo MA, mas a mensagem de Merlin não depende da entrada e nos preocupamos com o tempo de execução de Arthur.
fonte