Mi chiedo come calcolare lo spazio complessità del trie struttura. Visto che ho fatto il calcolo che se la profondità(lunghezza della parola) è N e Dimensione del Modello K(per le piccole alfabeti 26) e numero di parole: W Come per la mia comprensione, dovrebbe essere: K^N
Considerando che molti posti dove è scritto che è WxKxN.
Potrebbe, per favore, più elaborato, che è corretto e Come?
Peggiore dei casi, si dovrebbe essere O(K^N)
Supponiamo che la lunghezza delle parole è 1, quindi un singolo array di dimensione k sarebbe sufficiente.
Ex : "b" (posizione = 1) k = [null, puntatore ad un altro array di dimensione k, null, null, null,, ........]
Supponiamo che la lunghezza di parola è 2, quindi abbiamo bisogno di avere un array di dimensione k per ciascuno dei personaggi che sono alla prima posizione nella parola
Ex: 'ba'
livello 1 ('b') : [null, puntatore a un array (consente di chiamare Z) nel livello 2, null, null, null, ......]
livello 2: Z (Secondo carattere 'a') : [puntatore ad un altro array di dimensione k, null, null, .......]
Diciamo che sono l'inserimento di 'bc', quindi stiamo andando ad avere un altro array di dimensione k per 'c' in posizione 3 (Supponendo che si sta inserendo 'a' a 0, quindi 'b' a 1, e così via)
Così, ad ogni livello 0, abbiamo un array di dimensione k (dimensioni a livello 0: K), al livello 2, abbiamo k array di dimensione k (dimensioni a livello 1: k^2), al livello 3 abbiamo un k^2 numero di array di dimensione k (formato livello 3: k^3), e così via.
Quindi lo spazio complessità sarà k + k^2 + k^3 + ..... k^N (N è la lunghezza della parola). Questo è il caso peggiore di complessità.
