algorithm - 哪个搜索更快，二分搜索还是使用前缀树？

Question

假设我有一个字符串列表和这些字符串的前缀树，我想找到一个给定键的字符串，哪个更快？二分查找还是前缀树查找？

为什么以及时间复杂度是多少？

谢谢！

Answer 1

这两种技术都有其优点和缺点：

后缀树

• 优点：
  • O(N) 构建复杂度
  • O(M) 搜索长度为 M 的模式
  • 它们允许在线构建
• 缺点：
  • 空间效率低
  • 真正复杂的构造算法

二分查找（带后缀数组）

• 优点：
  • 您可以在 O(N) 时间内对字符串数组进行排序
  • 节省空间（内存减少五倍（至少））
  • 简单直接的构造算法
• 缺点：
  • 他们不支持在线建设
  • O(M lg N) 时间在 N 个字符串中搜索长度为 M 的模式（这可以减少到 O(M+lg N) 但这仍然比后缀树慢一点）

这两种数据结构都非常强大。如果您的应用程序需要快速搜索，并且提供的空间足够，那么肯定会选择后缀树。但是如果空间很重要，那么后缀数组（二进制搜索）是你唯一的选择......