Qual è la complessità della creazione di uno trie di un elenco di parole e qual è la complessità della ricerca di altri set di parole in quel trie? Devo usare trie per la ricerca di stringhe, quando ho hashtable?Trie complessità e ricerca
La complessità della creazione di un trie è O(W*L), dove W è il numero di parole, e L è una lunghezza media della parola: è necessario eseguire L ricerche in media per ciascuna delle W parole del set.
Lo stesso vale per la ricerca di parole successive: si eseguono i passaggi L per ciascuna delle parole W.
Hash inserzioni e ricerche hanno la stessa complessità: per ogni parola è necessario controllare l'uguaglianza, che prende O(L), per la complessità complessiva di O(W*L).
Se è necessario cercare parole intere, la tabella hash è più semplice. Tuttavia, non è possibile cercare le parole in base al loro prefisso utilizzando una tabella hash; Se le ricerche basate su prefissi non ti interessano, usa una tabella hash; altrimenti, usa un trie.
se sto cercando l'intera parola in hashtable, ho bisogno di qualche buona funzione di hash e dovremmo fare molta attenzione quando si definisce la funzione di hash. Correggetemi se ho torto ... – Varun
@var A causa dell'uso diffuso delle stringhe come chiavi delle tabelle hash, sono state inventate ottime funzioni di hashing per le stringhe. Una rapida ricerca su Internet ti darà una mezza dozzina di suggerimenti eccellenti. Vorrei andare con quello che usa Microsoft, o quello incorporato nelle stringhe Java, perché sono stati ottimizzati molto. – dasblinkenlight