Zastanawiam się, jak obliczyć przestrzenną złożoność struktury trie. Jak już obliczył, jeśli głębokość(długość słowa) jest równa N, a rozmiar szablonu K(dla małych alfabetów 26) i liczba słów: W Według mojego zrozumienia, to powinno być: K^N
Podczas gdy w wielu miejscach jest napisane, że to WxKxN.
Nie mógłbyś, proszę, wyjaśnić, że poprawnie i jak?
W najgorszym wypadku, to musi być O(K^N)
Załóżmy, że długość słowa jest równa 1, więc wystarczy jeden tablicy rozmiaru k.
Przykład : 'b' (pozycja = 1) k = [null, indeks na innej tablicy rozmiaru k, null, null, null, ........]
Załóżmy, że długość słowa jest równa 2, to musimy mieć tablicę typu k dla każdego z symboli, które znajdują się na pierwszej pozycji w słowie
Przykład: "ba"
poziom 1 ('b') : [null, wskaźnik na tablicę (nazwijmy go Z) na poziomie 2, null, null, null, ......]
poziom 2: Z (drugi symbol "a") : [indeks na innej tablicy rozmiaru k, null, null, .......]
Załóżmy, wstawiamy "bc", wtedy mamy inną tablicę typu k dla " c "w pozycji 3 (przy założeniu, że wkładasz" a "0", a następnie "b" w 1 i tak dalej)
Dlatego na każdym poziomie 0, czyli macierz o rozmiarze K (rozmiar na poziom 0: Do), na 2 poziomie mamy K tablicy typu K (rozmiar na poziomie 1: do^2), na poziomie 3 mamy do^2 liczba w tablicy typu K (rozmiar na poziomie 3: do^3), i tak dalej.
W ten sposób złożoność przestrzeni będzie równa k + k^2 + k^3 + ..... k^N (N-długość słowa). To jest najgorszy czasowa złożoność.
