Grande o da mesa de hash vs. árvore de pesquisa binária

Question

O que levaria mais tempo?

Imprima todos os itens armazenados em uma árvore de pesquisa binária em ordem classificada ou imprima todos os itens armazenados em uma tabela de hash em ordem classificada.

Levaria mais tempo para imprimir os itens de uma tabela de hash em ordem classificada porque uma tabela de hash nunca é resolvida correta? E um BST é?

Answer 1

Você está certo. Hashtables são classificados por alguma função de hash, não por sua ordem de classificação natural, então você teria que extrair todas as entradas o (n) e classificá -las o (nLogn), enquanto você pode atravessar uma árvore de pesquisa binária em ordem natural em O ( N).

No entanto, observe que em Java, por exemplo, há um LinkedHashSet e LinkedHashmap, o que oferece algumas das vantagens do hash, mas que podem ser atravessadas na ordem em que foi adicionado, para que você possa classificá -lo e ser capaz de atravessá -lo naquele Ordem classificada, além de extrair itens por hash.

Answer 2

Correto, uma tabela de hash não é "classificada" da maneira que você provavelmente deseja. Os elementos nas tabelas de hash não são totalmente classificados, geralmente, embora o arranjo seja frequentemente meio que na vizinhança. Mas eles são organizados de acordo com a função de hash, que geralmente é extremamente diferente para frases semelhantes. Não é uma espécie de qualquer métrica que um humano usaria.

Se a principal coisa que você está fazendo com sua coleção é imprimi -la em ordem classificada, é melhor usar algum tipo de BST.

Answer 3

Uma árvore de pesquisa binária é armazenada de uma maneira que, se você fizer uma primeira travessia de profundidade, encontrará os itens em ordem classificada (supondo que tenha uma função de comparação consistente). O grande o de simplesmente retornar itens já na árvore seria o grande o de atravessar a árvore.

Você está correto sobre as tabelas de hash, elas não são classificadas. De fato, para enumerar tudo em uma tabela de hash simples, você deve verificar cada balde para ver o que está lá, retire -o e depois classificar o que você recebe. Muito trabalho para obter uma lista classificada disso.

Answer 4

Correto, a impressão de dados classificados armazenados em uma tabela de hash seria mais lenta porque uma tabela de hash não é classificada dados. Apenas oferece uma maneira rápida de encontrar um item específico. Dentro "Grande notação o"Dizem que o item pode ser encontrado em tempo constante, ou seja, o (1) tempo.

Por outro lado, você pode encontrar um item em uma árvore de pesquisa binária em "tempo logarítmico" (O (log n)) porque os dados já foram classificados para você.

Portanto, se seu objetivo é imprimir uma lista classificada, é melhor ter os dados armazenados em uma ordem classificada (ou seja, uma árvore binária).

Apreciar,

Robert C. Cartaino

Answer 5

Isso traz algumas perguntas interessantes. Uma árvore de pesquisa ainda é mais rápida, considerando o seguinte?

1. Incorporando o tempo de configuração para a tabela de hash e o BST?
2. Se o algoritmo hash produzir uma lista classificada de palavras. Tecnicamente, você pode criar uma tabela de hash que use um algoritmo que o faça. Nesse caso, a velocidade da tabela BST versus a tabela de hash teria que se resumir à quantidade de tempo necessária para preencher a tabela de hash na ordem classificada.

Answer 6

Verifique também as considerações relacionadas da lista de skip vs. Árvore Binária: Skip List vs. Tree Binária