Trie 数据结构 space 在 Java 中的用法

Question

我只想仔细检查 Trie 数据结构在最坏情况下可能具有的总数 space。我认为它是 O(N*K)，其中 N 是节点总数，K 是字母表的大小（指向其他尝试），但人们一直告诉我它是 O(K^L)，其中 K 是字母表的大小，L 是平均字长，但是那些空指针是否用完 space in Java 中的内存？例如，如果其中一个节点只有总大小 K 中的 3 branches/points 。它是否使用 K space ？或者只有 3 个？以下是Java

中的Trie实现

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个节点，那么显然它的space复杂度是O(N*K)。这解释了空指针 do 占据它们的 space 的事实。实际上，无论数组条目是 null 还是任何其他值，在内存消耗方面都不会改变任何内容。

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

Answer 2

我想提供更多有关的详细信息。

trie的每个节点消耗的内存是一样的，是null还是不是。一个数组只存储指针，自初始化以来它总共有 space 个。虽然每个节点都有自己的内存，但这是一个实现细节，我们正在讨论渐近分析，所以我们不考虑节点实现占用的内存。

O(N*K) 是完整 trie 中的节点数（每个节点 N 有 K 个子节点）。这是正确的，但是您正在考虑节点的数量并且您事先不知道。如果您知道这一点，则可以将每个节点使用的内存（实现细节）加起来，然后您将计算出您的 trie 使用的确切内存量。在这种情况下，大 O 符号甚至可能没有意义 (?)。

你能知道的是L（键的平均长度）和K（字母表的大小），所以你用这些来分析复杂度。如果你做数学运算，你会发现 K^L 实际上只占 trie 的最后一层（取 K=2 和 L=3，这将给出一个高度为 4 的二叉树，并且2^3 = 最后一层有 8 个节点，总共有 15 个节点）。最后一层没有给出 trie 中的节点总数，但我们正在谈论渐近分析，只有有效位很重要。所以你有 O(K^L).

Trie 数据结构 space 在 Java 中的用法

Trie data structure space usage in Java

java

algorithm

trie

space-complexity