Mă întreb cum de a calcula spațiul complexitatea trie structura. Cât am fost în calcul faptul că în cazul în care adâncimea(lungimea cuvântului) este N și Model de Dimensiune K(pentru litere mici, 26) și numărul de cuvinte: W Ca pe înțelegerea mea, ar trebui să fie: K^N
Întrucât multe locuri în care este scris că este WxKxN.
Ai putea, te rog elaborate pe ceea ce este corect și Cum?
Mai rău caz, ar trebui să fie O(K^N)
Să presupunem că lungimea cuvântului este 1, atunci o singură matrice de dimensiune k ar fi suficientă.
Ex : "b" (poziția = 1) k = [null, pointer la o altă matrice de dimensiune k, null, null, null, ........]
Să presupunem că lungimea cuvântului este 2, atunci avem nevoie pentru a avea o matrice de dimensiune k pentru fiecare dintre personaje, care sunt la prima poziție în cuvânt
Ex: "ba"
nivelul 1 ("b") : [null, pointer la o matrice (permite numesc Z) la nivelul 2, null, null, null, ......]
nivelul 2: Z (Doua caractere 'a') : [pointer la o altă matrice de dimensiune k, null, null, .......]
Să zicem că suntem la introducerea 'bc', atunci vom avea o altă matrice de dimensiune k pentru "c", la poziția 3 (Presupunând că sunt introducerea 'o de la 0, atunci" b " la 1 și așa mai departe)
Deci, la fiecare nivel 0, avem o matrice de dimensiune k (dimensiunea de la nivelul 0: K), la nivelul 2 trebuie k matrice de dimensiune k (dimensiunea de la nivelul 1: k^2), la nivelul 3, avem un k^2 numărul de matrice de dimensiune k (dimensiunea de la nivelul 3: k^3), și așa mai departe.
Astfel spațiul de complexitatea va fi k + k^2 + k^3 + ..... k^N (N este lungimea cuvântului). Acest lucru este cel mai rău caz complexitatea timp.
