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

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 に答える