Pourquoi la complexité spatiale de cet algorithme est O (1)

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!

Answer 1

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.)

Answer 2

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.

Pour plus de lecture, voir Appel de queue