遍历字典树(Trie)的时间复杂度是否为O(26n)

你给出的打印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());
    }
}

针对你提出的「遍历时间复杂度为O(26n)，其中n为Trie层数，最坏满树场景下估算成立」的判断，直接给出结论：该判断不合理，核心问题是混淆了Trie的层数和总节点数两个参数。

具体分析 #

• 代码的执行逻辑：每个Trie节点调用print方法时，都会固定执行26次子节点存在性判断，存在则递归调用对应子节点的print方法。因此总操作次数和Trie的总节点数成正比。
• 正确的时间复杂度估算：如果将参数n定义为Trie的总节点数量，O(26n)的估算完全正确，通常复杂度表示会省略常数系数，直接写为O(n)。
• 原估算的错误点：你将参数n定义为Trie的层数，在你假设的「每层填满26个节点的最坏满树」场景下，Trie的总节点数为 `1 + 26 + 26² + ... +26^n = O(26^{n)，是指数级规模，此时遍历的时间复杂度为O(26}(n+1))，和你提出的线性级O(26n)完全不是一个量级。

内容的提问来源于stack exchange，提问作者JamesR