algorithm - 获取以下递归实现的时间复杂度

Question

/* 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 是树中的节点数？？

Answer 1

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

否则 Master's theorem

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