4

我看到一篇谈论 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);
}

但我想知道如何计算算法的时间复杂度，有人可以帮我吗？

4

2 回答 2

4

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

如果你的树是平衡的，（参见AVL，红黑树）高度是log(n)，因此算法的总复杂度是O(log(n))。

于 2014-06-07T12:37:40.287 回答
3

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

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;
}

countMatchesPQ被要求height of tree times - 1。让我们将树的高度称为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 树，treap 等）如果树是不平衡的，在更坏的情况下 h may be up to N

所以复杂度N可以表示为

对于平衡二叉树：O(N logN)
更准确地说，对于平衡树来说，它是实际的 h(N + N/2 + N/4...) ，因此应该是 2hN
对于不平衡二叉树：O(N 2 )
更准确地说，它是 平衡树的实际 h(N + N-1 + N-2...)，因此应该是 hx N x (N+1) / 2

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

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

于 2014-06-07T12:53:01.470 回答