Eu estou querendo saber como calcular o espaço a complexidade da estrutura trie. Como tenho vindo a calcular que, se a profundidade(comprimento de palavra) é N e Padrão de Tamanho K(para pequenos alfabetos 26) e número de palavras: W Conforme meu entendimento, deve ser: K^N
Considerando que muitos lugares está escrito que é WxKxN.
Você poderia por favor explique o que é correto e Como?
Pior caso, deve ser O(K^N)
Vamos supor que o comprimento da palavra é 1 e, em seguida, um único array de tamanho k seria suficiente.
Ex : 'b' (posição = 1) k = [null, ponteiro para outra matriz de tamanho k, null, null, null,, ........]
Vamos supor que o comprimento da palavra é 2, então nós precisamos ter uma matriz de tamanho k para cada um dos personagens que estão na primeira posição na palavra,
Ex: 'ba'
nível 1 ("b") : [null, ponteiro para uma matriz (vamos chamar-lhe Z) no nível 2, null, null, null, ......]
nível 2: Z (Segundo caractere 'a') : [ponteiro para outra matriz de tamanho k, null, null, .......]
Vamos dizer que estamos inserindo 'bc' então nós vamos ter outro array de tamanho k para " c " na posição 3 (Supondo que você está inserindo 'um' 0 'b' a 1 e assim por diante)
Assim, em cada nível 0, temos uma matriz de tamanho k (tamanho no nível 0: K), no nível 2, temos k da matriz de tamanho k (tamanho no nível 1: k^2), no nível 3, temos um k^2 número da matriz de tamanho k (tamanho no nível 3: k^3), e assim por diante.
Assim, o espaço complexidade será k + k^2 + k^3 + ..... k^N (N é o comprimento da palavra). Este é o pior caso de tempo de complexidade.
