Big O di Hash Table vs. Binary Search Albero

Question

Il che sarebbe necessario più tempo?

stampare tutti gli elementi memorizzati in un albero binario di ricerca in modo ordinato o stampare tutti gli elementi memorizzati in una tabella hash in modo ordinato.

Ci vorrebbe più tempo per stampare le voci di una tabella hash in modo ordinato, perché una tabella di hash non è mai allineati corretta? e un BST è?

Answer 1

Hai ragione. Hashtables sono ordinati per alcune funzioni di hash, non dalla loro ordinamento naturale, in modo che avrebbe dovuto estrarre tutte le voci O (n) e O (N log N) ordinare, mentre si può attraversare un albero binario di ricerca in ordine naturale a O ( N).

Nota, tuttavia, che in Java, per esempio, c'è un LinkedHashSet e LinkedHashMap che vi dà alcuni dei vantaggi di Hash, ma che possono essere attraversati nell'ordine in cui è stato inserito, così si potrebbe risolvere la cosa ed essere in grado di attraversare in che modo ordinato, così come l'estrazione di elementi da hash.

Answer 2

Una corretta, una tabella di hash non è "risolto" nel modo in cui probabilmente si vuole. Elementi in tabelle hash non sono del tutto completamente ordinati, di solito, anche se la disposizione è spesso tipo di nei pressi di una specie. Ma sono disposti secondo la funzione hash, che è solitamente molto diversi per frasi simili. Non è una specie da tutto il metrica un essere umano avrebbe usato.

Se la cosa principale che si sta facendo con la vostra collezione è la stampa in modo ordinato, si sta meglio fuori usando un certo tipo di BST.

Answer 3

Un albero binario di ricerca è memorizzato in un modo che se si fa una profondità prima di attraversamento, si trovano gli oggetti in modo ordinato (supponendo che hai un coerente funzione di confronto). The Big O semplicemente di restituzione degli articoli già nella struttura sarebbe il Big O di attraversare l'albero.

Hai ragione su tabelle hash, non sono ordinati. Infatti, al fine di elencare tutto ciò che in una tabella hash pianura, si deve controllare ogni secchio per vedere che cosa è in là, estrarlo, quindi ordinare quello che si ottiene. Un sacco di lavoro per ottenere un elenco ordinato di questo.

Answer 4

stampa ordinato Correggere i dati, memorizzati in una tabella hash sarebbe più lento a causa di una tabella di hash non è ordinato dati. E 'appena ti dà un modo rapido per trovare un elemento particolare. In " notazione O-grande " si dice che l'oggetto può essere trovato in tempo costante, vale a dire O (1).

D'altra parte, è possibile trovare un elemento in un albero binario di ricerca in "tempo logaritmico" (O (log n)), in quanto i dati sono già stati ordinati per voi.

Quindi, se si obiettivo è quello di stampare un elenco ordinato, siete molto meglio avere i dati memorizzati in un modo ordinato (vale a dire un albero binario).

Enjoy,

Robert C. Cartaino

Answer 5

Questo porta ad un paio di domande interessanti. È un albero di ricerca ancora più veloce tenendo conto dei seguenti?

1. Incorporando il tempo di setup sia per la tabella hash e il BST?
2. Se l'algoritmo di hash produce un elenco ordinato di parole. Tecnicamente, si potrebbe creare una tabella hash che usa un algoritmo che fa. Nel qual caso la velocità del BST contro la tabella di hash avrebbe dovuto venire giù alla quantità di tempo necessario per compilare la tabella hash in modo ordinato.

Answer 6

Verificate anche le considerazioni correlate di Skip Lista vs. Albero binario: Skip Lista vs. albero binario