使用 Balanced BST 查找时间复杂度的字典
Dictionary using Balanced BST lookup time complexity
我在 geeksforgeeks 中阅读了一篇关于如何使用平衡 BST 实现字典的文章，发现了这一行：
If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
我不明白这怎么会是 O(M*logn)，考虑到平衡 BST 始终保持最大高度 O(logn)，这不应该是 (logn) 吗？
这句话摘自在字典中搜索单词的上下文：
Trie is an efficient data structure for searching words in dictionaries, search complexity with Trie is linear in terms of word (or key) length to be searched. If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. So it is much faster than BST.
在 BST 中，这些单词将被存储为一个节点得到一个单词。
虽然在节点的平衡 BST 中您需要访问 O(log) 个节点以在最坏的情况下找到目标值，但是将节点的字符串与目标字符串进行比较也需要时间。由于单词的最大长度为 ，因此每个单独的字符串比较的最坏情况时间复杂度为 O()。由于这样的比较发生在每个访问的节点上，因此总复杂度为 O(log)。
我在 geeksforgeeks 中阅读了一篇关于如何使用平衡 BST 实现字典的文章，发现了这一行：
If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
我不明白这怎么会是 O(M*logn)，考虑到平衡 BST 始终保持最大高度 O(logn)，这不应该是 (logn) 吗？
这句话摘自在字典中搜索单词的上下文：
Trie is an efficient data structure for searching words in dictionaries, search complexity with Trie is linear in terms of word (or key) length to be searched. If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. So it is much faster than BST.
在 BST 中，这些单词将被存储为一个节点得到一个单词。
虽然在节点的平衡 BST 中您需要访问 O(log) 个节点以在最坏的情况下找到目标值，但是将节点的字符串与目标字符串进行比较也需要时间。由于单词的最大长度为 ，因此每个单独的字符串比较的最坏情况时间复杂度为 O()。由于这样的比较发生在每个访问的节点上，因此总复杂度为 O(log)。