小智 87
按顺序,预订和后序遍历是深度优先遍历.
对于图,深度优先遍历的复杂度为O(n + m),其中n是节点数,m是边数.
由于二叉树也是图形,因此这同样适用.这些深度优先遍历中的每一个的复杂度是O(n + m).
由于在二进制树的情况下可以源自节点的边的数量被限制为2,所以二进制树中的最大总边数是n-1,其中n是节点的总数.
然后复杂度变为O(n + n-1),即O(n).
jer*_*ome 12
你好
我今天在课堂上被问到这个问题，这是一个好问题！我将在这里解释，并希望我的更正式的答案得到审查或更正错误。:)
@Assaf 的观察也是正确的，因为二叉树遍历递归地访问每个节点一次。
但是！由于它是一种递归算法，您通常必须使用更高级的方法来分析运行时性能。在处理顺序算法或使用 for 循环的算法时，使用求和通常就足够了。因此，下面是对这种分析的更详细解释，供好奇的人使用。
如前所述，
T(n) = 2*T(n/2) + 1
其中 T(n) 是在您的遍历算法中执行的操作数（按顺序、前序或后序没有区别。
有两个T(n)因为中序、前序和后序遍历都在左右子节点上调用自己。因此，将每个递归调用视为T(n)。换句话说，**左 T(n/2) + 右 T(n/2) = 2 T(n/2) **。“1”来自函数内的任何其他恒定时间操作，例如打印节点值等。（老实说，它可以是 1 或任何常数，并且渐近运行时间仍然计算为相同的值。解释如下。）。
这种递归实际上可以使用大师定理使用大 theta 进行分析。所以，我将在这里应用它。
T(n) = 2*T(n/2) + 常数
其中常量是某个常量（可以是 1 或任何其他常量）。
使用大师定理，我们有 T(n) = a*T(n/b) + f(n)。
所以，a=2, b=2, f(n) = 常数，因为f(n) = n^c = 1，那么c = 0因为f(n)是常数。
从这里，我们可以看到a = 2和b^c = 2 ^0 = 1。所以，a>b^c或2>2^0。所以，c < logb(a)或0 < log2(2)
从这里我们有 T(n) = BigTheta(n^{logb(a)}) = BigTheta(n^1) = BigTheta(n)
如果您有BigTheta（N）不famliar，它是“相似”（请多多包涵:)）到O（n）的，但它是运行时一个“更紧密的结合”或更紧密近似。因此，BigTheta(n)既是最坏情况的O(n)，也是最佳情况的BigOmega(n)运行时。
我希望这有帮助。小心。
T(n) = 2T(n/2)+ c
T(n/2) = 2T(n/4) + c => T(n) = 4T(n/4) + 2c + c
类似地 T(n) = 8T(n/8) + 4c+ 2c + c
....
....
最后一步... T(n) = nT(1) + c(从0到h(树的高度)的2的幂之和)
所以复杂度是 O(2^(h+1) -1)
但 h = log(n)
所以，O(2n - 1) = O(n)
O(n),我会说.我正在做一棵平衡的树,适用于所有树木.假设你使用递归,
T(n)= 2*T(n/2)+ 1 ---------->(1)
左子树的T(n/2)和右子树的T(n/2)和验证基本情况的'1'.
在简化(1)时,您可以证明遍历(有序或预订或后序)的顺序为O(n).
二叉树的深度优先遍历的阶数为 O(n)。
Algo -- <b>
PreOrderTrav():-----------------T(n)<b>
if root is null---------------O(1)<b>
return null-----------------O(1)<b>
else:-------------------------O(1)<b>
print(root)-----------------O(1)<b>
PreOrderTrav(root.left)-----T(n/2)<b>
PreOrderTrav(root.right)----T(n/2)<b>
如果算法的时间复杂度是 T(n)，那么它可以写成 T(n) = 2*T(n/2) + O(1)。如果我们应用回代，我们将得到 T(n) = O(n)。