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