Jsem zvědav, jak vypočítat prostor složitost trie struktury. Jak jsem již počítají s tím, že v případě, že hloubka(délka slova), je N a Velikost vzorku K(pro malé abecedy, 26) a počet slov: W Dle mého chápání, by to mělo být: K^N
Vzhledem k tomu, že na mnoha místech je napsáno, že je WxKxN.
Mohl byste, prosím, upřesnit co je správné a Jak na to?
Nejhorším případě, by to mělo být O(K^N)
Předpokládejme, že délka slova je 1, pak jednotlivá pole o velikosti k, by byl dostatečný.
Ex : "b" (pozice = 1) k = [null, ukazatel na další pole o velikosti k, null, null, null,, ........]
Předpokládejme, že délka slova je 2, pak musíme mít pole o velikosti k. pro každou z postav, které jsou na první pozici ve slově
Ex: "ba"
úroveň 1 ("b") : [null, ukazatel na pole (umožňuje volat to Z) v úrovni 2, null, null, null, ......]
úroveň 2: Z (Druhý znak "a") : [ukazatel na další pole o velikosti k, null, null, .......]
Řekněme, že jsme vkládání "bc", pak budeme mít další pole o velikosti k, pro " c "na pozici 3 (za Předpokladu, že vkládání" a "na 0, pak" b " na 1 a tak dále)
Takže na každé úrovni 0, máme pole o velikosti k (velikost na úroveň 0: K), na úrovni 2 máme k pole o velikosti k (velikost na úrovni 1: k^2), na úrovni 3 máme k^2 počet pole o velikosti k (velikost na úrovni 3: k^3), a tak dále.
Takže paměťová složitost bude k + k^2 + k^3 + ..... k^N (N je délka slova). To je nejhorší časovou složitost.
