如何计算自定义前缀树打印所有单词函数的时间复杂度大O？

这个函数通过深度优先遍历前缀树的所有节点，每到达一个单词结束标记就输出对应拼接好的单词，复杂度计算逻辑如下： #

理论最优复杂度（不考虑字符串拼接的实现差异） #

如果忽略字符串传递、拼接的额外开销，或者你用了可变结构（比如列表）来传递当前前缀，复杂度为：

• 首先前缀树的所有T个节点会被恰好访问1次，这部分开销为O(T)
• 每次遇到单词结束标记时，打印单词的总开销等于所有存储单词的总字符数之和S，这部分开销为O(S)
  由于前缀树的节点数T一定小于等于S（每个字符至少对应一个节点，公共前缀会减少节点总数），因此整体可以简化为 O(S)，S是前缀树中所有存储单词的总字符数之和。

你当前Python实现的实际复杂度 #

Python中的字符串是不可变对象，你每次递归执行word+letter时，都会完整复制现有word的所有字符再拼接新字符，会引入额外的复制开销：
总拼接开销等于所有根节点到非根节点的路径长度之和，最坏情况是所有单词无公共前缀、所有单词长度均等于最长单词长度L_max，此时总复杂度为 O(k * L_max²)，其中k是单词总数，L_max是最长单词的长度；如果单词的公共前缀较多，实际开销会对应降低。
如果要优化到理论最优的O(S)，可以把传递前缀的方式换成可变列表：递归前append新字符，当前节点的递归全部完成后pop，打印时用''.join(word_list)生成字符串即可，避免每次递归都复制整个前缀字符串。 #

内容的提问来源于stack exchange，提问作者carlosdafield