1 
/* Function to get diameter of a binary tree */
int diameter(struct node * tree)
{
   /* base case where tree is empty */
    if (tree == 0)
     return 0;

  /* get the height of left and right sub-trees */
  int lheight = height(tree->left);
  int rheight = height(tree->right);

  /* get the diameter of left and right sub-trees */
  int ldiameter = diameter(tree->left);
  int rdiameter = diameter(tree->right);


  return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}


int height(struct node* node)
{
   /* base case tree is empty */
   if(node == NULL)
       return 0;

   /* If tree is not empty then height = 1 + max of left
      height and right heights */   
    return 1 + max(height(node->left), height(node->right));
}

使用此实现查找树直径的时间复杂度为 O(n^2)，其中 n 是树中的节点数？

4

2 回答 2

0

让D()表示diameter()和H()表示height()。为方便起见，我们假设二叉树Complete Binary Tree的左子树和右子树具有相同数量的元素。N让我们也假设二叉树中有元素。现在直径函数的时间复杂度可以用下面的递推关系来表示。

D(N) = 2D(N/2) + 2H(N/2) + c1  ----- 1

由于 中的以下递归调用diameter()， 

  int lheight = height(tree->left);
  int rheight = height(tree->right);

  int ldiameter = diameter(tree->left);
  int rdiameter = diameter(tree->right);

现在让我们分析一下height()，

表示时间复杂度的递推关系height()为，

H(N) = 2H(N/2) + c2  ------ 2

由于 中的以下递归调用height()，

return 1 + max(height(node->left), height(node->right));

现在H(N) = O(N logN)通过在 2 上应用主定理。

将其代入 1，我们得到，

D(N) = 2D(N/2) + c3 N logN + c1   ------ 3

使用主定理求解3D(N) = O(N logN) ，我们得到.

所以递归函数的复杂度diameter()是O(N logN)

于 2013-06-19T12:08:44.703 回答
0

它是 O(n^2) 因为高度计算也是递归的。您可以编写递归关系并解决它。

否则根据Master 定理

您可以看到 f(n) 是线性的，因此 c = 1 因此，当 a 为 4（递归使用 4 次）且 b 为 2（在树的一半上）时，复杂度为 a 到 b 的对数

于 2013-06-19T06:27:25.313 回答