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是对人口稠密的特里树中节点数的估计，而在O（N * K）中，明确给出了节点数。