Me estoy preguntando cómo calcular el espacio de la complejidad de la estructura trie. Como he estado calculando que si la profundidad(longitud de la palabra) es N y el Patrón de Tamaño K(para pequeñas alfabetos 26) y el número de palabras: W Según mi entender, debería ser: K^N
Mientras que muchos lugares está escrito que es WxKxN.
Por favor podría elaborar sobre lo que es correcto y Cómo?
Peor de los casos, debe ser S(K^N)
Supongamos que la longitud de la palabra es 1, entonces una sola matriz de tamaño k sería suficiente.
Ex : 'b' (=1) k = [null, puntero a otra matriz de tamaño k, null, null, null, ........]
Supongamos que la longitud de la palabra es 2, entonces tenemos que tener una matriz de tamaño k para cada uno de los personajes que están en la primera posición en la palabra
Ex: 'ba'
nivel 1 ('b') : [null, puntero a una matriz (vamos a llamarlo Z) en el nivel 2, null, null, null, ......]
nivel 2: Z (Segundo carácter 'a') : [puntero a otra matriz de tamaño k, null, null, .......]
Digamos que estamos insertando 'bc', entonces vamos a tener otra matriz de tamaño k 'c' en la posición 3 (Suponiendo que se va a insertar 'a' en 0, 'b' en la 1 y así sucesivamente)
Así, en cada nivel, 0, tenemos una matriz de tamaño k (tamaño en el nivel 0: K), en el nivel 2 tenemos k de la matriz de tamaño k (tamaño en el nivel 1: k^2), en el nivel 3 tenemos un k^2 número de matriz de tamaño k (tamaño en el nivel 3: k^3), y así sucesivamente.
De modo que el espacio de la complejidad será k + k^2 + k^3 + ..... k^N (N es la longitud de la palabra). Este es el peor caso de tiempo de complejidad.
