递归层次遍历二叉树的时间复杂度是多少？

Question

在这个geeksforgeeks链接中，他们将递归层序遍历的时间复杂度描述为O(n^2)。

时间复杂度：最坏情况下为O(n^2)。对于一个倾斜的树，printGivenLevel()需要O(n)的时间，其中n是倾斜树中节点的数量。因此，printLevelOrder()的时间复杂度是O(n) + O(n-1) + O(n-2) + .. + O(1)，即O(n^2)。我不太明白这一点。

请有人帮助我理解。

- Walt

Answer 1

对于这样的倾斜树：

1
 \
  2
   \
   ...
     \
      N

这棵树的深度为N，因此下面的函数将从1运行到N。

printLevelorder(tree)
for d = 1 to height(tree)
   printGivenLevel(tree, d);

也就是说，

printGivenLevel(tree, 1);
printGivenLevel(tree, 2);
...
printGivenLevel(tree, N);

printGivenLevel(tree, depth)需要O(depth)的时间，因为它每次都从根节点开始。

时间复杂度为:

O(1) + O(2) + ... + O(N) = O(N^2)

- iForests

---

顺便提一下，在实现BFS算法时，确保使用队列以O(n)的时间复杂度运行。 - iForests

Answer 2

当然。

注意这是一个等差数列。我们知道它的求和如下：

n + (n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2

但是：

n * (n - 1) / 2 = (n^2 - n) / 2

然而，我们知道与线性项相比，二次（平方）项占主导地位，并且1/2是一个常数因子，两者简化了表达式，如下所示：

首先，去掉常数因子：

O((n^2 - n) / 2) = O(n^2 - n)

接下来，保留主要项：

O(n^2 - n) = O(n^2)

这就是你达到这种复杂性的方式。

- dionyziz

---

抱歉没有说得很清楚。我的问题不是关于AP sum，而是这个方程式从哪里来的，以及在for循环中运行从1到树的高度（在最坏情况下将为n）的printlevel，两个疑问：1.它不应该是O(n) * printlevel的时间复杂度吗？2.printlevel的时间复杂度表达式（O）（n）+ O（n-1）从哪里来？ - Walt