Trie, Hash, MinADFA

Trie的搜索复杂度是 O(length(strkey)),Hash表,计算Hash的复杂度也是O(length(strkey)),但是,仔细分析一下:

  1. Trie因为每读一个字符,要做一次状态转移,就有一次(随机)访存操作,计算 strkey 的 Hash 不需要每个字符都随机访存,从这一点看,Hash胜出
  2. Hash 可能会有冲突,而 Trie 没有冲突,这一点,Trie 胜出
  3. 可以在 Trie 上应用 DFA Minimization 算法,生成一个 Minimum Acyclic DFA,再加一些额外算法,可以节省更多内存(有可能超过100倍),同时可以用 O(length(strkey)) 的时间复杂度把 strkey 映射到它在 MinADFA 中的字典序的序号。
作者:
该日志由 csdn-whinah 于2012年09月07日发表在HashTable, 自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: Trie, Hash, MinADFA
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。