二叉树中函数maxheight的复杂性

Question

功能：

MAX-HEIGHT(node) 
  if(node == NIL) 
      return -1;
  else 
     return max(MAX-HEIGHT(node.leftChild), MAX-HEIGHT(node.rightChild)) + 1;

假设我们有N个节点，我们用MAX-HEIGHT(root).调用该函数

我认为这个函数的复杂性是O（N），因为我们需要访问每个节点。但是，我不确定，我不能严格证明这一点。请给我一个很好的解释，为什么它是O（N），如果是O（N），为什么不是O（N）。

那么，复杂性是什么？

谢谢。

Answer 1

在一般情况下，对于平衡的二叉树

T(n) = 2T(n/2) + Θ(1);

每次递归调用都会给你两个大小一半的问题。根据主定理，这将评估为T（n）=Θ（n）

在最坏的情况下，每个节点只有一个孩子。

T(n) = T(n-1) + Θ(1)

评估为T（n）=Θ（n）

Answer 2

你应该问的问题是：

• N在我的数据结构中表示什么（二叉树）
• 在确定结构的高度之前，我需要经过多少N.

这里，N表示树中的节点数，在返回高度之前必须经历所有节点。

因此，您的算法在O（N）

Answer 3

这是另一种方法。我在其中一些计算中可能出错，所以请纠正我。

我们可以写

T(n) = 2 T(n/2) + c for all n > 1, where c is some constant. And 
T(n) = 1 when n = 1

So T(n) = 2 T(n/2) + c, now start substituting T(n/2) and move one

=> T(n) = 2 [ 2 T(n/4) + c ] + c
=> T(n) = 2^2T(n/4) + 2c

Now substitute t(n/4) as well
=> T(n) = 2^2[2 T(n/8) + c] + 2c
=> T(n) = 2^3T(n/8) + 3c

Now assume that if we keep dividing like this, at some point we will reach 1 i.e., when n/2^k = 1, then T(1) = 1

=> T(n) = 2^kT(n/2^k) + kc

Now since we know that n/2^k = 1
=> k = log n (I am representing log as base 2)

Therefore substitute k value in above T(n) equation to get
=> T(n) = 2^(log n) T(1) + c log n
=> T(n) = n T(1) + c log n (Check log rule on how we got n for first coefficient)
=> T(n) = n + c log n (since T(1) = 1)

因此，T（n）= O（n），因为n在增长率中控制log n。