Как вычислить временную сложность алгоритма наименьшего общего предка?

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

но мне было интересно, как вычислить временную сложность алгоритма, кто-нибудь может мне помочь?

4

algorithm c++least-common-ancestor time-complexity

Решение

Другие решения

Сложность LCA является O(h) где h это высота дерева. Верхняя граница высоты дерева O(n), где n обозначает количество вершин / узлов в дереве.

Если ваше дерево сбалансировано, (см. AVL, красное черное дерево) высота порядка log(n)следовательно, общая сложность алгоритма O(log(n)),

4

Источник

Accepted Answer

Наихудший случай для этого алгоритма будет, если узлы покидают узлы.

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 (РБ дерево, треп и т. Д.)
Если дерево не сбалансировано, в худший случай 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²

Ваш алгоритм не использует память. Используя немного памяти для сохранения пути, вы можете значительно улучшить свой алгоритм.

3