首页 > 试题广场 > 在ASC算法team日常开发中,常常面临一些数据结构的抉择,
[单选题]
在ASC算法team日常开发中,常常面临一些数据结构的抉择,令人纠结。目前大家在策划一个FBI项目(Fast Binary Indexing),其中用到的词汇有6200条,词汇长度在10-15之间,词汇字符是英文字母,区分大小写。请在下面几个数据结构中选择一个使检索速度最快的:
  • 二叉搜索树,比较函数开销:1次运算/每字符
  • 哈希表,hash算法开销:10次运算/每字符
  • 链表,比较函数开销:1次运算/每字符
  • TRIE树,寻找子节点开销:1次运算/每字符
推荐
注解:又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
编辑于 2015-02-04 20:54:26 回复(2)
对于TRIE树(字典树)来说,能在O(len)的时间内查出该单词是否存在,而且空间占用少。
发表于 2018-12-07 14:57:53 回复(0)
哈希的复杂度不是o(1)吗?
发表于 2018-10-12 08:45:10 回复(1)
其实这几个选项我都有点看不懂,最后面的1次运算/每字符是什么意思?
发表于 2018-08-31 15:22:16 回复(0)
注解:又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
发表于 2019-06-19 20:29:34 回复(0)
字典树
发表于 2018-09-14 14:49:27 回复(0)
哈希的复杂度不是o(1)吗?
发表于 2017-05-28 18:18:51 回复(1)
这题用trie树空间复杂度要炸裂啊。。。。
发表于 2017-01-26 10:47:44 回复(4)
trie单词查找树
发表于 2016-10-08 08:49:39 回复(0)
D
百度百科http://baike.baidu.com/link?url=PYYfck8aXrrJhPjyi1Ay52qBXccRDmdOY4BvLAu_hOxOFEA7yWYqux9LGPLWVJFjChZPNDYeIEOL5eKGm8jRejdW1Fdu0LFyZpxW2LUIQJxkPZSPylBiAcqb2TFK0rZTvs9wrxiwuYzPo0yNrOo8-q
发表于 2015-07-01 16:48:40 回复(0)