如何计算这个递归函数的时间复杂度

Question

我目前正在学习算法和数据结构课程，但我在理解如何计算此函数的复杂性时遇到一些困难，因为它涉及另一个递归函数中的递归函数。请问有人可以指导一下吗？

设 x 为二叉搜索树 (BST) 的根，假设节点数为 n。

免责声明：我很清楚这个功能效率很低。这些函数仅供说明之用。

伪代码：

countForEach(x){ //prints the number of nodes for each subtree of the tree rooted at x
    if(x != NIL){
        CountForEach(x.left)
        CountForEach(x.right)
        print(countRec(x))
    }
}

countRec(y) //returns the number of nodes in the subtree rooted in y
    if(y == NIL):
        return 0
    else:
        return countRec(y.left) + countRec(y.right) + 1

我知道

countRec(x)

的时间复杂度为 θ(m)，其中 m 是以 x 为根的子树中的节点数，

countRec(y)

被

countForEach(x)

调用 n 次，其中 n 是节点数以 x 为根的树。 阻止我找到解决方案的是 m 随着

CountForEach

的执行而减少。

Answer 1

在评论中，您已经得出了如果树是“退化”的结果，即每个节点只有一个子节点，除了（单个）叶节点：𝑛+（𝑛−1）+... +3+2+1 = 𝑛(𝑛+1)/2，即 θ(𝑛²)。就 𝑛 而言，这是最坏的情况。 最好的情况是当树是完美的时，即不存在只有一个子节点并且所有叶子都处于同一级别的节点。

令 ℎ 为完美二叉树的高度；节点数 𝑛 等于 2

ℎ+1

−1. 以自上而下的方式计算

countRec

的调用次数，我们得到树的每一层的这些项：

      2

ℎ+1

−1       + 2

1

⋅(2^ℎ−1)       + 2

2

⋅(2^ℎ−1−1)       + 2

3

⋅(2^ℎ−2−1)       + ...

      + 2

ℎ

将每一项写成 2 的两次幂的减法：

      = 2

ℎ+1

−2⁰       + 2

ℎ+1

−2¹       + 2

ℎ+1

−2²       + 2

ℎ+1

−2³       + ...

      + 2

ℎ+1

−2^ℎ 添加条款：

      = (ℎ+1)2

ℎ+1

−(2^ℎ+1−1)       = ℎ2

ℎ+1

+1 就像这棵完美的树 𝑛=2

ℎ+1

−1 一样，这意味着：       = (log

2

(𝑛+1)−1)(𝑛+1) + 1 即 θ(𝑛log𝑛) 总之，我们可以说最坏情况的时间复杂度是 θ(𝑛²)，最好情况的时间复杂度是 θ(𝑛log𝑛)。

Answer 2

令 n 为二叉树中的节点总数。

CountForEach 函数：在最坏的情况下，它只会访问每个节点一次。因此，该函数的时间复杂度为 O(n)。
强大的textcountRec函数：该函数的时间复杂度在最坏的情况下也是O(n)，因为它只遍历每个节点一次。
由于这两个函数都是为树中的每个节点调用的，因此所提供代码的总体时间复杂度为 O(n * n) = O(n^2)。

总而言之，代码的时间复杂度是二叉树中节点数量的二次方。