遍历 trie 的时间复杂度

Question

会不会是 O(26n)，其中 26 是字母表的字母数，n 是 trie 的级别数？例如，这是打印 trie 的代码：

public void print() 
{
    for(int i = 0; i < 26; i++) 
    {
        if(this.next[i] != null) 
        {
            this.next[i].print();
        }
    }
    if(this.word != null) 
    {
        System.out.println(this.word.getWord());
    }
}

所以看着这段代码让我觉得我的时间复杂度的近似值在最坏的情况下是正确的，即 26 个节点已满 n 级。

Answer 1

我不熟悉 trie，但大 O 符号主要是描述运行时间或资源消耗相对于输入大小的增长速度。我的想法只是参考图表上曲线的一般形状，而不是图表上的确切点。 O(1) 看起来像一条平线，而 O(n) 看起来像一条 45 度角的线，等等

来源：https://medium.com/dataseries/how-to-calculate-time-complexity-with-big-o-notation-9afe33aa4c46

现在是问题中的算法。我不熟悉 trie，但乍一看我会说它是 O(1)（常数时间），因为循环的迭代次数是常数（总是 26）。然而，在循环中它有 this.next[i].print() 这可以根据它的复杂性完全改变答案，并揭示了一个我们需要知道的重要问题：什么是 n .

我假设 this.next[i] 与 this 属于同一类型，使 this.next[i].print() 成为一种递归调用。在这种情况下，完成执行所需的时间将全部取决于必须迭代（访问）的实例数。该算法类似于 Depth First Search 但不能防止无限递归。这可能基于关于 next[i] 个实例（节点）的一些已知附加信息，例如一个实例仅被最多 1 个其他实例引用。在这种情况下，运行时复杂度约为 O(n)，其中 n 是实例或节点的数量。

...假设 this.word.getWord() 也在恒定时间内运行。如果它取决于其他一些词输入，运行时间也可能是 O(n * w)，其中 n 是节点数，w 是词的大小。

Answer 2

Would it be O(26n) where 26 is the number of letters of the alphabet and n is the number of levels of the trie?

没有。必须访问 trie 中的每个节点，并且为每个节点执行 O(1) 工作（忽略可归因于处理 children 的工作，这是单独计算的）。 children 的数量在 per-node 的基础上无关紧要，只要它受常数限制（例如 26）即可。

一共有多少个节点？一般多于 trie 中存储的单词数，并且可能更多。对于一个naively-implemented，完美平衡，根以下n层的完整trie，每一层的节点数是前一层的26倍，因此节点总数为1 + 26 + 26² + ... + 26ⁿ。即 O(26ⁿ⁺¹) == O(26ⁿ) == O(2ⁿ)，或级别数中的“指数”，这也对应于其中存储的最长单词的长度。

但是人们更有可能对根据存储在 trie 中的单词数量来衡量复杂性感兴趣。通过仔细的实施，可以只为这些单词和两个或更多这些单词共有的每个最大初始子串设置节点。在这种情况下，每个节点都有零个 children 或至少两个，因此对于 w 个总字数，节点总数受 w[ 限制=37=] + w/2 + w/4 + ...，收敛到 2w.因此，遍历具有这些结构属性的特里树的成本为 O(2w) == O(w).

此外，稍加思考，可以得出结论，我描述的特定结构属性并不是真正需要 O(w) 遍历.

遍历 trie 的时间复杂度

Time complexity of travel a trie

java

tree

trie

nodes

data-structures