如何计算含嵌套递归的二叉搜索树函数的时间复杂度？

核心分析思路 #

我们的目标是计算所有countRec调用的总时间，因为countForEach的时间开销完全来自于它发起的countRec调用。已知每次countRec(x)的时间是Θ(m)（m为x子树的节点数），且countRec被调用n次（每个节点作为根各一次），所以总时间就是所有节点的子树节点数之和对应的时间复杂度。

分情况推导 #

最坏情况（链表式BST） #

当BST退化为链表（每个节点只有左/右子节点）时，每个节点x的子树节点数m等于从x到链表末尾的节点总数：

• 根节点的m = n
• 第二个节点的m = n-1
• ...
• 最后一个节点的m = 1
  总和为：n + (n-1) + ... + 1 = n(n+1)/2，对应的时间复杂度是Θ(n²)。这也是这个低效函数的最坏情况开销。

平衡BST情况 #

对于平衡二叉搜索树（如AVL树、红黑树），每层的节点数大致是上一层的2倍，每个节点的子树节点数之和满足：

• 第k层（从根开始算第1层）的每个节点子树节点数约为n/(2^(k-1))，该层共有2^(k-1)个节点
• 每层的总开销为2^(k-1) * (n/(2^(k-1))) = n
• 总层数为log₂n，所以总和为n * log₂n，对应的时间复杂度是Θ(nlogn)。

总结 #

这个嵌套递归函数的时间复杂度取决于BST的结构：

• 最坏情况（非平衡链表结构）：Θ(n²)
• 平衡结构：Θ(nlogn)
  由于题目标注该函数效率极低，通常指的是最坏情况的Θ(n²)复杂度。

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