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

Question

在 THIS geeksforgeeks link 中，他们将递归级别顺序遍历的时间复杂度描述为 O(n^2)。

时间复杂度：O(n^2) 在最坏的情况下。对于倾斜树，printGivenLevel() 需要 O(n) 时间，其中 n 是倾斜树中的节点数。所以 printLevelOrder() 的时间复杂度是 O(n) + O(n-1) + O(n-2) + .. + O(1) 即 O(n^2)。我不清楚。

谁能帮我理解一下。

Answer 1

当然可以。

注意这是等差数列。 We know 总和如下：

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

但是：

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

但是，we know 与线性项相比，二次（平方）项支配表达式，并且 1 / 2 是常数因子，两者都将表达式简化如下：

首先，去掉常数因子：

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

接下来，保留主导词：

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

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

Answer 2

对于像这样的倾斜树：

这棵树的深度是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)

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

What is time complexity of recursive level order traversal of a binary tree

algorithm

recursion

binary-tree

time-complexity