假设我有一个字符串列表和这些字符串的前缀树，并且我想在给定键的情况下定位一个字符串，哪个更快？二分查找还是前缀树查找？
为什么以及时间复杂度是多少？
Thanks!
这两种技术都有其优点和缺点：
后缀树
- Advantages:
- O(N) 构建复杂度
- O(M) 搜索长度为 M 的模式
- 他们允许在线施工
- Drawbacks:
二分查找（带后缀数组）
- Advantages:
- 您可以在 O(N) 时间内对字符串数组进行排序
- 节省空间（内存减少五倍（至少））
- 简单直接的构造算法
- Drawbacks:
- 他们不支持在线构建
- O(M lg N) 时间在 N 个字符串中搜索长度为 M 的模式（这可以减少到 O(M+lg N)，但这仍然比后缀树慢一点）
这两种数据结构都非常强大。如果您的应用程序需要快速搜索，并且提供的空间足够，那么一定要使用后缀树。但如果空间很重要，那么后缀数组（二分搜索）是你唯一的选择......
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
