Estrutura de dados com pesquisa, inserção e exclusão no tempo amortizado

25

Existe uma estrutura de dados para manter uma lista ordenada que suporta as seguintes operações em tempo amortizado?O(1)

  • GetElement (k) : retorna o ésimo elemento da lista.k

  • InsertAfter (x, y) : insira o novo elemento y na lista imediatamente após x.

  • Excluir (x) : remova x da lista.

Nas duas últimas operações, você pode assumir que x é fornecido como um ponteiro diretamente na estrutura de dados; InsertElement retorna o ponteiro correspondente para y. InsertAfter (NULL, y) insere y no início da lista.

Por exemplo, começando com uma estrutura de dados vazia, as seguintes operações atualizam a lista ordenada, como mostrado abaixo:

  • InsertAfter (NULL, a) [a]
  • InsertAfter (NULL, b) [b, a]
  • InsertAfter (b, c) [b, c, a]
  • InsertAfter (a, d) [b, c, a, d]
  • Excluir (c) [b, a, d]

Após essas cinco atualizações, GetElement (2) deve retornar d, e GetElement (3) deve retornar um erro.

AT
fonte
2
Em Algoritmos ótimos para indexação de listas e classificação de subconjuntos (1989), encontrei solução para este problema. Ω(log nlog log n)
AT
2
@ Rafael: Eu acho que ele quer dizer o elemento que seria chamado se a estrutura de dados fosse uma matriz. Matrizes suportam a primeira operação em O (A[k] mas não na segunda; as listas vinculadas suportam a segunda operação em O ( 1 ), mas não a primeira. O(1)O(1)
JeffE 21/12/12
2
Além disso, árvores binárias balanceadas suportam ambas as operações em . O(logn)
JeffE
11
@ Rafael: Editado para esclarecer.
JeffE
2
@JeffE, o array dinâmico suporta os dois primeiros em amortizado tempo (cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf)O(1)
Diego

Respostas:

33

NÃO.

Fredman e Saks provaram que qualquer estrutura de dados que suporta essas operações requer pelo menos tempo amortizado por operaçãoΩ(logn/loglogn). (Esta é a referência [1] no artigo de Dietz que você mencionou em seu primeiro comentário.) O limite inferior é válido nomodelo de computação de sonda de célulamuitopoderoso, que considera apenas o número de endereços de memória distintos acessados ​​pela atualização e consulta algoritmos.

Sem algumas suposições adicionais sobre as operações de atualização e consulta, a estrutura de dados de Dietz é a melhor possível (pelo menos até fatores constantes).

JeffE
fonte
3
@ AT: Esse limite nunca foi "provado errado". Há situações em que não se aplica, mas essa é uma afirmação totalmente diferente!
Raphael
5
@ AT: O limite inferior de classificação foi provado em um modelo de computação muito mais fraco, ou seja, árvores de decisão binária. O limite foi "provado errado" ao desenvolver algoritmos mais rápidos que não podem ser descritos como árvores de decisão binárias. Para provar que o limite inferior de Fredman e Saks está errado, você precisará criar um algoritmo mais rápido que não acesse a memória . Boa sorte.
21412 JeffE
@JeffE e Raphael; revise minha outra resposta e confirme / negue meu resultado quando tiver a chance. Obrigado.
AT
6

Parece que o barreira foi superada modificando a análise da técnica do cronograma.Ω(lognloglogn)

O novo [inferior] limite ) foi provado para problemas semelhantes no modelo de célula-sonda [1]. Da leitura desse artigo; Entendo que esse limite também se aplica aoproblema derepresentação de lista.Ω(logn)


[1] Patrascu, Mihai e Erik D. Demaine. "Limites inferiores logarítmicos no modelo de sonda celular." SIAM J. Comput. 35, n. 4 (abril de 2006): 932–963. doi: 10.1137 / S0097539705447256.

AT
fonte
11
Este limite inferior tem para palavras de tamanho constantes-, enquanto que o anterior um limite inferior é de palavras logaritmicamente porte. Ω(logn/loglogn)
Yuval Filmus
De fato. Além disso, você pode confirmar que esse limite se aplica ao problema de representação de lista com palavras de tamanho constante?
AT
11
Θ(logn/loglogn) Ω(logn)