Pourquoi la complexité spatiale de cet algorithme est O (1)
-
09-10-2019 - |
Question
Salut à tous: je lis l'algorithme ci-dessous pour trouver le plus petit ancêtre commun de deux noeuds dans un arbre de recherche binaire.
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int );
/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;
/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;
if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}
Notez que la fonction ci-dessus suppose que n1 est inférieur à n2. complexité du temps: O (n) complexité Espace: O (1)
cet algorithme est récursive, je sais que lors de l'appel d'un appel de fonction récursive, les arguments de la fonction et d'autres registres connexes est poussé à la pile, de sorte que l'espace supplémentaire est nécessaire, d'autre part, la profondeur récursive est liée à la taille ou la hauteur de l'arbre, disons n, est-il plus logique d'être O (n)?
Merci pour toutes les explications ici!
La solution
Bien que vous avez raison de dire que cette mise en œuvre récursive de l'algorithme nécessite O (n) l'espace en raison de l'espace de pile nécessaire, il utilise seulement l'espace récursion queue, ce qui signifie qu'il peut être réimplémentée à utiliser O (1) avec une boucle :
int leastCommanAncestor(struct node* root, int n1, int n2)
while (1)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;
/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;
if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
root = root->left;
else if(root->data < n1 && root->data < n2)
root = root->right;
}
}
(Notez que else
doit être ajoutée pour maintenir la sémantique inchangée.)
Autres conseils
Cet algorithme implique récursion queue. Dans le contexte de votre question, le cadre de la pile de l'appelant peut être réutilisé par le callee. En d'autres termes, toute la séquence imbriquée d'invocations de fonction vont faire est de passer le résultat comme une bucket brigade. Par conséquent, un seul cadre de pile est réellement nécessaire.