我想知道如何计算的空间复杂的trie结构。 正如我已经计算，如果深度(长的词)是N和图形的大小K(对于小的字母26)和数字：W 按我的理解是，它应该是：K^N
而许多地方，它是书面的，是WxKxN.
能否请你详细说明这是正确和如何？
0
最糟糕的是，它应该是O(K^N)
让我们假设这个词的长度为1，然后一个单一的系列大小k就足够了。
例如：'b'的位置(位置=1)k=[空，指针指向另一个系列大小k,null,null,null, ........]
让我们假设这个词的长度为2,然后我们需要有一系列大小k每个字都在第一位置的词
例如：'ba'
1级('b'):[空，指阵列(可以称它Z)级别2,null,null,null，......]
2级：Z(第二字'a'):[指针指向另一个系列大小k,null,null，.......]
让我们说我们是插入题'，那么我们会有另外一系列大小k'c'的位置3(假设你是插入'a'at0,then'b'at1和以上)
因此，在每个级别0,我们有一系列大小k(大小在0级：K)中，在第2级，我们已k列的大小k(大小在1级：k^2)，在3级，我们有一个k^2号阵的大小k(大小在3级：k^3)，等等。
所以空间复杂性将 k + k^2 + k^3 +..... k^N (N词的长度)。 这是最糟糕的情况时的复杂性。