了解英语词典中有大约20万个单词,而字母表只有26个字母左右。
了解英语词典中有大约20万个单词,而字母表只有26个字母左右。
q
来说,存储26个子节点指针是有点疯狂的,因为在q
之后的字符几乎不可能是除了u
以外的其他字符。Wolfram Alpha 表示,单词的平均长度为 5.1 个字符 http://www.wolframalpha.com/input/?i=average+english+word+length
如果 L=26,字母表中的字母数目, 而 K=5.1,则英语单词的平均长度
=> 我预计空间复杂度大约在 O(L^K) 左右 (L 的 K 次方)
实际语言中的实现可能会有所不同,我想。
L^k
的数量假设没有共同的前缀。前缀树的整个意义在于利用共同的前缀。快速搜索显示实证结果范围在(N*K)/4
到(N*K)/3
个节点之间,其中N
是单词数量,K
是单词的平均长度。 - Jim Mischel