假如我有一个字符串列表与这些字符串的preFIX树，我想找出给定一个键一个字符串，其中之一是来得更快？二进制搜索或preFIX树搜索？

Suppose I have a list of strings and a prefix tree of those strings, and I would like to locate a string given a key, which one is more faster? binary search or prefix tree search?

为什么和什么时间复杂度？

Why and what's the time complexity?

谢谢！

推荐答案

这两种技术都有自己的优势，他们的缺点：

Both techniques have their advantages, and their drawbacks:

后缀树

优点： O（N）建设的复杂性 O（M）的搜索长度为M 的模式 在他们允许在线建设 Advantages: O(N) building complexity O(M) search of a pattern of length M They allow online construction 在浪费空间 在非常复杂的构造算法

二进制搜索（后缀阵列）

优点： 您可以排序的字符串数组中的O（N）时间 在节省空间的（五次较少的内存（至少）） 简单明了的构造算法 Advantages: You can sort the string array in O(N) time Space efficient (five times less memory (at least)) Simple and straightforward construction algorithms 在它们不支持网上建 0（M LG N）时间来搜索长度为M N串间的模式（这可以减少到O（M + LG N），但是，这仍然比后缀树慢一点）

这两个数据结构是真的很强大。如果你的应用需要快速搜索，并提供了空间足够的话，肯定去的后缀树。但是，如果空间的问题，那么后缀阵列（二进制搜索）是你唯一的选择......

Both of these data structures are really powerful. If your application requires fast searching, and the space supplied is enough, then definitely go for suffix trees. But if the space matters, then suffix array(binary search) is the only choice you have...