Árvores equilibradas simples com O (1) concat?

Respostas:

5

Você pode criar trivialmente uma estrutura de dados com O (1) tempo de concatenação amortizado , apenas reinserindo tudo de uma árvore na outra na concatenação (que tem custo de O (n log n), exatamente o mesmo usado na construção dessa árvore em o primeiro lugar, então o tempo total ainda é O (n log n)), mas isso é trapaça.

Na pior das hipóteses, O (1), os autores afirmam que foi um problema em aberto para qualquer estrutura de dados; portanto, acho que você não encontrará uma resposta fácil.

Alexandre Passos
fonte
1
Não tenho certeza se Brodal et al. significava que era um problema aberto, mesmo em um cenário efêmero. Você está falando sobre a frase no resumo que faz referência a "um problema aberto colocado por Kaplan e Tarjan"? Nesse caso, acho que está claro no contexto desse artigo que a K&T estava dizendo que a pergunta estava aberta em uma estrutura puramente funcional.
Jbapple
Fiz o download do artigo, mas ele afirma claramente que "Eles [K&T] perguntaram se a operação de junção pode ser implementada em O (1) pior caso, mesmo em um cenário efêmero, enquanto suporta pesquisas e atualizações em tempo logarítmico".
Blaisorblade
Bom ponto, Blaisorblade. Eu perdi essa frase.
Jbapple # 10/10
Esta solução trivial está realmente correta? É óbvio para mim que funcionará apenas se uma determinada árvore for concatenada com outra apenas uma vez. Se eu aplicar a mesma construção à concatenação recursiva de listas de singleton, obtenho complexidade , que corresponde à complexidade no caso de árvore. O ( n log n ) O ( n log 2 n )nO(nlogn)O(nlog2n)
Geoffrey Irving
4

Eu baixei o artigo que você mencionou e ele responde "não", pelo menos no momento da publicação do artigo. Isso é por duas razões:

  1. é necessário um artigo para revisar adequadamente os trabalhos relacionados, e eles o fazem na introdução, com um resumo na Fig. 1, que diz "não". Pelo menos, se foi publicado em uma conferência respeitável, mas parece que sim (Brodal é citado algumas vezes em "Estruturas de dados puramente funcionais", de C. Okasaki, uma referência sobre o assunto).

    No entanto, eles mencionam no texto um algoritmo com tempo de busca O (log n log log n) e concatenação no tempo O (1), esboçado no artigo da K&T no STOC '96. Pode ser interessante para você.

    • o desafio aberto da K&T que eles resolvem é sobre dicionários com concatenação O (1) e O (log N) pesquisar / inserir / excluir, mesmo para estruturas efêmeras.

O ponto 1. também garante que você possa simplesmente procurar documentos citando este para encontrar resultados posteriores, eles precisariam citá-lo.

Se a questão tivesse relevância prática (mas não deveria ser), acredito que fatores constantes são mais importantes que a diferença entre O (1) e O (log N) (conforme discutido na Introdução aos algoritmos de Sedgewick), então você precisa procurar apenas referências para o caso de uso do seu aplicativo.

Blaisorblade
fonte
ESOP é uma conferência respeitável, se é isso que você quis dizer.
Charles Stewart
Essa foi minha pergunta, mas para a ESA, onde o artigo é publicado, não para a ESOP (talvez você quis dizer isso). Eu não tinha certeza se poderia confiar na classificação da conferência. Esta página classificação não oficial sugere que também ESA é bastante respeitável: www3.ntu.edu.sg/home/assourav/crank.htm
Blaisorblade