Je me demande comment calculer l'espace de la complexité de la trie de la structure. Comme je l'ai calculé que si la profondeur(longueur de mot) est N et la Taille du Motif K(pour les petits alphabets 26) et le nombre de mots: W Selon ma compréhension, il convient de: K^N
Alors que de nombreux endroits, il est écrit qu'il est WxKxN.
Pourriez-vous donner des précisions sur ce qui est correct et Comment?
Pire des cas, il convient de O(K^N)
Supposons que la longueur des mots est 1, alors un seul tableau de taille k serait suffisant.
Ex : "b" (position = 1) k = [null, pointeur vers un autre tableau de taille k, null, null, null, ........]
Supposons que la longueur du mot est de 2, alors nous avons besoin d'avoir un tableau de taille k pour chacun des personnages qui sont à la première position dans le mot
Ex: 'ba'
niveau 1 ('b') : [null, pointeur vers un tableau (permet de l'appeler Z) dans le niveau 2, null, null, null, ......]
niveau 2: Z (Deuxième caractère 'a') : [pointeur vers un autre tableau de taille k, null, null, .......]
Disons que nous sommes insertion " bc " ensuite, nous allons avoir un autre tableau de taille k 'c' à la position 3 (en Supposant que vous êtes l'insertion de " a " à "0", " b " à 1 et ainsi de suite)
Ainsi, à chaque niveau 0, nous avons un tableau de taille k (de la taille au niveau 0: K), au niveau 2, nous avons k de la matrice de taille k (de la taille au niveau 1: k^2), au niveau 3, nous avons un k^2 nombre de tableau de taille k (de la taille au niveau 3: k^3), et ainsi de suite.
Afin que l'espace de la complexité sera k + k^2 + k^3 + ..... k^N (N est la longueur de mot). C'est le pire moment de la complexité.
