如何计算最小公元算法的时间复杂度？

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，红黑树)高度是log(n)的阶，因此算法的总复杂度是O(log(n))。

Answer 2

该算法最坏的情况是节点是兄弟左节点。

Node *LCA(Node *root, Node *p, Node *q)
{
  for root call countMatchesPQ;
  for(root->left_or_right_child) call countMatchesPQ; /* Recursive call */
  for(root->left_or_right_child->left_or_right_child) call countMatchesPQ;
  ...
  for(parent of leave nodes of p and q) call countMatchesPQ;
}

height of tree times - 1调用

countMatchesPQ。设树的高度为h。

现在检查辅助函数

的复杂度

int countMatchesPQ(Node *root, Node *p, Node *q) {
  Search p and q in left sub tree recursively
  Search p and q in right sub tree recursively
}

所以这是一个广泛的搜索，最终的复杂度是N，其中N是树中的节点数。

将两个观测值相加，算法的总复杂度为

O(h * N)

如果树是平衡的，h = log N (RB树，树等)如果tree不平衡，在最坏的情况下 h may be up to N

用N表示的复杂度可以用

表示

对于平衡二叉树:O(N logN)
更精确地说，它是实际的h(N + N/2 + N/4…)表示平衡树，因此应该是2hN
对于非平衡二叉树:O(N²)
更精确地说，它是实际的h(N + N-1 + N-2…)为平衡树，因此应该是h x N x (N+1)/2

所以最坏的情况复杂度是N²

你的算法不使用任何内存。通过使用一些内存来保存路径，你可以大大改进你的算法。