使用二进制搜索和Trie的复杂性

使用二进制搜索和Trie的复杂性

特里树的搜索时间为O（m ），二进制搜索的 时间为O（m log（n））。 对于任何合理的方法， 该空间都是渐近O（n
m），您可以在某些情况下使用压缩来减小 该空间
。从理论上讲，特里结构在内存上要好一些，但是在实践中，它隐藏了实现细节：存储指针所需的内存和潜在的不良高速缓存访​​问。

还有其他实现集合结构的选项-在大多数语言中，hashset和treeset是容易选择的。我会选择哈希集，因为它既高效又简单。