13

功能：

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)。

那么，复杂度是多少？

谢谢你。

4

3 回答 3

16

在平均情况下，对于平衡二叉树

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

每个递归调用都会给你两个问题，但大小只有一半。根据主定理，这将评估为 T(n) = Θ(n)

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

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

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

于 2013-10-05T21:34:59.353 回答
6

你应该问的问题是：

  • N 在我的数据结构中代表什么（二叉树）
  • 在确定结构的高度之前，我必须经过多少 N。

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

因此，您的算法在 O(N)

于 2015-12-09T14:18:04.657 回答
1

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

我们可以写

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 的主导地位。

于 2019-03-18T19:07:57.930 回答