Quale richiederebbe più tempo?Grande O di tabella hash vs albero di ricerca binaria
stampa tutti gli elementi memorizzati in un albero di ricerca binario in ordine o stampa tutti gli elementi memorizzati in una tabella hash in ordine.
È necessario più tempo per stampare gli elementi di una tabella hash in ordine perché non viene mai ordinata una tabella hash corretta? e un BST è?
Sei corretto. Gli hashlables sono ordinati per una qualche funzione di hash, non per il loro ordinamento naturale, quindi devi estrarre tutte le voci O (N) e ordinarle O (NlogN) mentre puoi attraversare un albero di ricerca binario in ordine naturale in O (N).
Si noti tuttavia che in Java, ad esempio, c'è un LinkedHashSet e LinkedHashMap che offre alcuni dei vantaggi di Hash ma che possono essere spostati nell'ordine in cui è stato aggiunto, in modo da poter essere ordinati e in grado di attraversalo in quell'ordine ordinato così come estrae gli oggetti per hash.
Corretto, una tabella hash non è "ordinata" nel modo desiderato. Gli elementi nelle tabelle hash non sono completamente ordinati, di solito, sebbene l'arrangiamento sia spesso simile a quello di un certo tipo. Ma sono organizzati secondo la funzione di hash, che di solito è molto diversa per frasi simili. Non è un tipo da qualsiasi metrica che un essere umano userebbe.
Se la cosa principale che si sta facendo con la raccolta è la stampa in ordine, è meglio utilizzare un tipo di BST.
Un albero di ricerca binario è memorizzato in modo che se si esegue un primo attraversamento di profondità, si troveranno gli articoli in ordine (presumendo che si disponga di una funzione di confronto coerente). Il Big O del semplice ritorno degli oggetti già nell'albero sarebbe il Big O di attraversare l'albero.
Sei corretto sulle tabelle hash, non sono ordinate. Infatti, per enumerare tutto in un semplice hash table, devi controllare ogni bucket per vedere cosa c'è dentro, estrarlo, quindi ordinare ciò che ottieni. Un sacco di lavoro per ottenere una lista ordinata da questo.
Correggere, stampare i dati ordinati memorizzati in una tabella hash sarebbe più lento perché una tabella hash non è dati ordinati. Ti dà solo un modo veloce per trovare un oggetto particolare. In "Big O Notation" si dice che l'oggetto può essere trovato in tempo costante, cioè O (1) tempo.
D'altra parte, è possibile trovare un elemento in un albero di ricerca binario in "tempo logaritmico" (O (log n)) perché i dati sono già stati ordinati per voi.
Quindi, se l'obiettivo è stampare un elenco ordinato, è molto meglio avere i dati memorizzati in un ordine ordinato (ad esempio un albero binario).
godere,
Robert C. Cartaino
Questo porta ad un paio di domande interessanti. Un albero di ricerca è ancora più veloce considerando quanto segue?
controllare anche le considerazioni correlate di Skip Lista vs. Albero binario: Skip List vs. Binary Tree