我使用链表(而不是像往常一样使用数组(实现了一个Trie我的TrieNode包含链接列表作为节点(而不是限制输入类型-英语、数字等(我想知道使用链表作为节点的Trie当前的复杂性是多少。谢谢
如果要检查长度为l的单词w是否在trie中，则最多需要检查trie的l级别。在每一层中，您需要使用线性搜索来检查当前节点是否有一个子节点，该子节点包含下一个所需的字母。需要迭代的子节点的最大数量是您正在使用的字母表的大小。
因此，我认为答案是O(l*|A|(，其中A是您使用的字母表，如果是小写拉丁字母A=A，b。。，y、 z；所以|A|=26。
我不会说我会使用链表或数组*作为trie的节点存储，因为两者都会使每个节点的搜索和插入都是O(n)，因此trie整体O(n * D)的复杂性接近O(A * D)，其中A和D分别是字母表长度和trie深度。
相比之下，每个节点的哈希图在我看来是trie的天真实现中最不复杂/最具性能的，因为它会将搜索和插入的复杂性降低到每个节点的O(1)和整体的O(D)。唯一额外的复杂性是调整地图的大小，但如果空间不是问题，您可以预先调整每个地图的大小以使其初始容量为A，从而无需动态调整地图大小。
*：这是基于对数组实现使用暴力搜索和插入。如果您可以创建字符到基于零的索引的静态1-1映射，那么使用数组可以实现相同的操作和空间复杂性，并且性能比使用哈希映射略好