在线 -
搜索 AIGC编程网
← 返回题目列表

字典树的时间和空间复杂度是多少？为什么它空间开销大？

高频 中等 第 11 / 26 题 更新于 2026/08/03
字典树Trie复杂度空间

简化版

时间：插入、查找、前缀匹配都是 O(L)（L 为字符串长度），和 Trie 里存了多少单词无关——这是 Trie 的最大优势。空间是它的短板：最坏 O(N × L × C)（N 个单词、平均长 L、字符集大小 C），因为每个节点都要为「所有可能的字符」预留子节点位置，大量指针是空的，稀疏浪费严重。所以 Trie 是典型的空间换时间。

详细版

操作复杂度说明
插入O(L)沿 L 个字符走一遍
查找单词O(L)同上
前缀匹配O(L)同上
空间O(节点数 × C)C 为字符集大小（数组实现）

为什么时间是 O(L) 且与单词数无关：查找不需要和其它单词比较，只是顺着目标串的字符逐个下降 L 步。无论 Trie 里有 100 个还是 1 亿个单词，查一个长度为 L 的词都只走 L 步。

为什么空间大：用定长数组实现时，每个节点都有 C（如 26）个子指针槽位，但大多数是空的。节点总数最坏可达「所有单词的字符总数」，每个又乘以 C，空间就上去了。

完整版教学

一、时间 O(L)：Trie 的核心竞争力

Trie 查找的时间只取决于被查字符串的长度 L，与集合里单词的数量完全无关。这一点很关键：

  • 哈希表查字符串：要先算整个串的哈希值（O(L)），还可能遇到冲突需要比较，平均 O(L) 但有冲突风险。
  • 平衡树（如 TreeMap）查字符串：O(log N) 次比较，每次比较又是 O(L)，总共 O(L log N)。
  • Trie：稳稳的 O(L)，没有哈希冲突、不随集合增大而变慢。

在「海量单词、频繁前缀查询」的场景，Trie 的 O(L) 稳定性是它被选用的根本原因。

二、空间为什么是短板

Trie 的空间开销来自两方面：

  1. 节点数量多：最坏情况下（单词间几乎没有公共前缀），节点总数接近「所有单词的字符总数」N×L。每个字符都可能是一个独立节点。
  2. 每个节点的子指针稀疏：用定长数组 TrieNode[26] 时，一个节点即使只有 1 个孩子，也占着 26 个指针的空间，其余 25 个是 null，白白浪费。字符集越大（如 Unicode 几万字符）浪费越夸张。

两者相乘，空间最坏 O(N × L × C)。这就是「空间换时间」——用大量空间换来了稳定的 O(L) 查询。

三、公共前缀能省多少空间

Trie 的省空间来自「公共前缀共享」。如果单词间前缀重合度高（如一堆 inter- 开头的词），前缀部分只存一份，能显著减少节点。所以：

  • 前缀重合度高（如字典单词、URL、IP）→ Trie 省空间且高效。
  • 前缀几乎不重合（如随机字符串）→ Trie 退化，节点数接近 N×L，空间浪费严重，此时不如哈希。

四、优化空间的手段

针对空间大的短板，有几种常见优化：

  • children 用哈希表代替定长数组：只存实际存在的孩子，消除稀疏浪费，代价是访问常数变大。
  • 压缩字典树（Radix Tree / Patricia Trie）：把「只有一个孩子的链」压成一条边（存字符串而非单字符），大幅减少节点数（见压缩 Trie 专题）。
  • 双数组 Trie（Double-Array Trie）：用两个数组紧凑编码，工业级实现（如分词库）常用，空间效率高。

五、和其它结构的取舍

  • 要前缀操作、稳定 O(L)、字典序遍历 → Trie（接受它的空间开销）。
  • 只要等值查找、省内存 → 哈希表。
  • 前缀重合度低、内存紧张 → 优先哈希或压缩 Trie。

六、常见误区与追问

考点正确口径
查找时间O(L)，L 是字符串长度
插入时间O(L)
空间与节点数和每个节点的孩子表示有关
total chars = 1,000,000
array children size = 26
space roughly nodes * 26 pointers

Trie 用空间换时间，换来的不是 O(1)，而是稳定的按字符长度查询。

  • 误区：Trie 查询是 O(1)。 必须逐字符向下走，复杂度是 O(L)，L 是字符串长度。
  • 误区：Trie 空间只等于单词数量。 空间取决于节点数，节点数和词库总字符数、公共前缀共享程度有关。
  • 误区：数组 children 总是最佳选择。 数组访问快但稀疏时浪费大，哈希表或压缩结构可能更合适。
  • 追问：公共前缀如何节省空间？ 相同前缀只存一条路径，多个单词在分叉前共享节点。
  • 追问：如何优化空间？ 可用哈希表孩子、压缩 Trie、双数组 Trie、位图加紧凑数组等。
  • 追问：为什么仍常用 Trie？ 它对前缀操作非常自然，时间稳定，不依赖哈希函数和碰撞处理。

七、加强记忆

Trie 时间 O(L)（插入/查找/前缀都是，与单词数无关，无哈希冲突、不随集合变大变慢）——这是它的核心优势。空间是短板：最坏 O(N×L×C)，因为节点多、且定长数组实现下每节点的 C 个子指针大多为空（稀疏浪费），字符集越大越浪费。本质是空间换时间。前缀重合度高则省空间高效，重合度低则退化。优化用哈希表存孩子、压缩 Trie、双数组 Trie。