java - Java中Trie数据结构空间使用

Question

我只想仔细检查 Trie 数据结构在最坏情况下可能拥有的总空间。我认为它是 O(N*K)，其中 N 是节点总数，K 是字母表的大小(指向其他尝试)，但人们一直告诉我它是 O(K^L)，其中 K 是字母表的大小和 L 是平均单词长度，但是这些空指针是否用完了 Java 中的内存空间？例如，如果节点之一只有总大小 K 中的 3 个分支/点。它是否使用 K 空间？或者只有 3 个？下面是Trie在Java

中的实现

class Trie {
     private Trie [] tries;

     public Trie () {
          // A size 256 array of Trie, and they are all null
          this.tries = new Trie[256]; // K = 256;
     }
}

Answer 1

如果单个节点的内存占用是K个引用，而trie有N个节点，那么显然它的空间复杂度是O(N*K)。这解释了空指针确实占用了它们的空间这一事实。实际上，数组条目是 null 还是任何其他值都不会改变内存消耗。

O(K^L) 是一个完全不同的度量，因为它使用不同的参数。基本上，K^L 是对人口稠密的 trie 中节点数量的估计，而在 O(N*K) 中，节点数量是明确给出的。