Trie（字典树）数据结构的空间复杂度如何正确计算？
2026-9-25
两个结论都是对的，分别对应Trie不同场景下的空间上界，具体推导逻辑如下：
1. O(K^N) 是理论最坏上界
这个结果对应的是完全满的Trie结构，适用场景是所有长度不超过N的、字符集内的组合字符串都被存入词库：
- 第一层（对应单词第一个字符）最多有K个节点
- 第二层每个第一层节点都扩展K个子节点，总共有K^2个节点
- 以此类推，第N层总共有K^N个节点
- 总节点数是等比数列求和 K + K^2 + ... + KN，量级就是O(KN)
这个上界非常极端，实际业务中几乎不可能遇到——比如你不可能把所有10位以内的英文字符串全存入词库，所以日常开发基本不会用这个上界做评估。
2. O(W×K×N) 是更贴近实际使用的上界
这也是绝大多数资料采用的结论，推导逻辑基于实际词库的特点：
- Trie的每个节点需要存储K个指针（对应字符集的每个可选字符），所以总空间和「总节点数 × K」成正比
- 实际词库中所有单词的总字符数上限是W×N：哪怕所有单词都没有任何公共前缀（比如所有单词的首字符、第二位到第N位字符全不重合），Trie的总节点数最多就是W×N
- 代入后总空间的量级就是O(W×K×N)
举个直观的对比例子：假设字符集是小写英文字母K=26，单词最大长度N=10，词库单词数W=10000，O(K^N)的结果是约1.4e14，而O(W×K×N)的结果只有2.6e6，后者显然更符合实际存储的情况。
内容的提问来源于stack exchange，提问作者Shakti Pravesh
相关产品推荐
相关产品推荐
