Qual è la complessità dello spazio per l'inserimento di un elenco di parole in una struttura dati Trie?

Lascia che w sia la quantità di parole nel trie. Quindi il limite O(w*m) è molto più utile, poiché rappresenta semplicemente la quantità massima di caratteri nel trie, che ovviamente è anche il suo limite di spazio.

In un certo senso, sì, O(n**m) è anche un confine corretto. È semplicemente abbastanza inutile nella maggior parte dei casi. Ad esempio, w = 200 parole con una lunghezza media di m = 100 in una dimensione alfabetica di n = 50 risulterebbe in O(50**100) , woot, non si adatta all'universo! ... mentre l'altro limite sarebbe O(200*100) .

Un trie stesso è un termine generico per una struttura dati che memorizza le chiavi implicitamente come percorso. Se cerchi google, vedrai che ci sono diverse implementazioni per una struttura di dati di ricerca in cui le chiavi sono memorizzate in questo modo, e quindi, ci saranno diverse complessità spaziali per ciascuno. Uno che mi viene in mente dai miei studi personali è il Trie R-Way, che usa una matrice di dimensione R (se le tue chiavi possono essere un qualsiasi carattere ASCII, R sarebbe 256) per memorizzare riferimenti a caratteri aggiuntivi nella chiave. Ogni nodo in questa struttura deve quindi allocare memoria per una matrice di dimensione R, quindi in termini di complessità spaziale, questo trie è O (RN) dove N è il numero di chiavi.

Un altro trie che ho studiato è il DeLabrandais trie, che usa liste collegate invece di matrici per memorizzare riferimenti a caratteri aggiuntivi nella chiave. Dal punto di vista della memoria, questo trie è effettivamente migliore perché alloca la memoria come necessario per ogni carattere aggiuntivo anziché allocare un pezzo gigantesco che sarà probabilmente parzialmente vuoto (assumendo una distribuzione non uguale di caratteri nelle chiavi memorizzate). Tuttavia, questa struttura richiederà più tempo per cercare un tasto, in quanto si perde l'accesso diretto agli array di riferimento e potrebbe ora dover attraversare un elenco collegato. Asintoticamente, il trie DLB (penso, ma potrebbe essere sbagliato) è ancora O (RN), ma il suo consumo di memoria è praticamente migliore nella maggior parte dei casi a causa della distribuzione non equa dei caratteri nelle chiavi che ho menzionato in precedenza.

Un altro modo di pensare è che lo spazio è O(kN) , dove k è il numero di possibili caratteri (supponendo che stiamo usando una matrice per memorizzare la mappatura), N è il numero di nodi in trie.

Mentre più significativamente, dal punto di vista del cliente, la complessità dello spazio è O(mn) , dove m è la lunghezza media delle stringhe inserite, n è il numero di parole. Questo calcolo presuppone il mapping di hashmap e O(mn) fornisce un upperbound perché non considera il prefisso comune.