给定文件中按字母顺序排序的单词的大列表，我需要编写一个程序，给定单词x，该程序确定x是否在列表中。预处理是可以的，因为我将在不同的输入上多次调用此函数。 优先事项：1.速度。2.记忆
我已经知道我可以使用（n是单词数，m是单词的平均长度）1.特里，时间是O（log（n）），空格（最好的情况）是O（log（n m）） ，空间（最坏情况）为O（n m）。 2.将完整列表加载到内存中，然后进行二进制搜索，时间为O（log（n）），空间为O（n * m）
我不确定tri的复杂性，如果错误，请纠正我。还有其他好的方法吗？
特里树的搜索时间为O（m ），二进制搜索的 时间为O（m log（n））。 对于任何合理的方法， 该空间都是渐近O（n m），您可以在某些情况下使用压缩来减小 该空间 。从理论上讲，特里结构在内存上要好一些，但是在实践中，它隐藏了实现细节：存储指针所需的内存和潜在的不良高速缓存访问。
还有其他实现集合结构的选项-在大多数语言中，hashset和treeset是容易选择的。我会选择哈希集，因为它既高效又简单。
