c++ - 如何计算最小公共(public)祖先算法的时间复杂度？

Question

我进入了一篇讲LCA算法的文章，代码很简单 http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
  if (!root) return 0;
  int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
  if (root == p || root == q)
    return 1 + matches;
  else
    return matches;
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (root == p || root == q) return root;
  int totalMatches = countMatchesPQ(root->left, p, q);
  if (totalMatches == 1)
    return root;
  else if (totalMatches == 2)
    return LCA(root->left, p, q);
  else /* totalMatches == 0 */
    return LCA(root->right, p, q);
}

但是我想知道如何计算算法的时间复杂度，谁能帮帮我？

Answer 1

LCA 的复杂性是 O(h) 其中 h 是树的高度。树高的上限是O(n)，其中n表示树中顶点/节点的数量。

如果你的树是平衡的，(参见 AVL ， red black tree )高度是 log(n) 的顺序，因此算法的总复杂度是 O(log (n))。