找到我写的这个函数的大 O 来打印 trie 中的所有单词

Question

我做了这个尝试

class Trie:
    def __init__(self):
        self.root = {}
        self.end = '[=10=]'

    def add(self,text):
        node = self.root 
        for letter in text:
            if letter in node:
                node = node[letter]
            else:
                node[letter]={}
                node = node[letter]
        node[self.end] = True
        
        
    def addAll(self,lst):
        for word in lst:
            self.add(word)

并制作了这个函数来打印 trie 中的所有单词

# takes in trie.root
def printWords(root,word=""):
    if root==True:
        print(word[:-1])
        return

    for letter in root:
        printWords(root[letter],word+letter)

如何找到这个函数的大OprintWords。

Answer 1

最差的时间复杂度是O(²)，其中是单词的个数，最长单词的大小。

word+letter 的计算时间复杂度为 O(len(word))。对于在 trie 中出现的给定单词，word+letter 的计算发生 O() 次，每次用一个字符扩展当前前缀，直到找到该单词。这给出了每个单词的时间复杂度 O(²)。

由于树中有单词，在最坏的情况下它们不共享任何前缀，总复杂度为 O(²)

Answer 2

大O应该是上限，换句话说，最坏的情况。

如果树存储 n 个长度为 m_0, m_1, ... , m_(n-1) 的单词，那么在最坏的情况下，它们会沿着树定义 n 个具有上述长度的不相交路径（实际上每条路径都是两个节点长于它所代表的单词，考虑到根节点和结束节点，但这对于大 O 的计算无关紧要）。因此，在最坏的情况下，您会 m_0 + m_1 + ... + m_(n-1) 调用 PrintWords.

但是，如果树存储了很多单词，上面的估计就过高了，因为一个节点可以拥有的子节点的数量是有限的（最多 27 个 - 每个字母一个 + 结束符号）。因此，如果我们用 h 表示树的高度（其中 h = max(m_0, m_1, ... , m_(n-1))，那么最多 min(m_0 + m_1 + ... + m_(n-1), 27×h) 调用 PrintWords。

由于我们正在计算渐近边界，我们可以假设 n 非常大，比 h 大得多，因此最坏的情况变成 27×h 调用，即 O(h)，其中 h 是最长单词的长度。

您可以更进一步，假设每个词的长度是有界的（自然语言中的词就是这种情况）。假设，你得到渐近界限是 O(1)。当然，这并不意味着手术很快，可能需要一段时间。但是，由于在最后一个假设下，树的大小是有界的（高度和宽度），因此您对恒定大小（可能非常大）的数据结构执行操作，因此它不会逐渐变得更复杂。你的树变得像一个单词词典 - 即使它包含某种语言的所有单词，它也必须有一个有限的大小，因此可以在有限的时间内完成所有单词。

找到我写的这个函数的大 O 来打印 trie 中的所有单词

Finding big O of this function I wrote to print all the words in a trie

python

algorithm

big-o

trie