algorithm - 二叉树中函数 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)

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

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

其计算结果为 T(n) = Θ(n)