Perché la complessità spaziale di questo algoritmo è O (1)

Question

Ciao a tutti:       ho letto l'algoritmo qui sotto per trovare il più basso antenato comune dei due nodi di un albero binario di ricerca.

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

  

Si noti che sopra presuppone che la funzione n1 è minore di n2.      Tempo di complessità: O (n) Spazio complessità: O (1)

questo algoritmo è ricorsiva, so che quando invoca una chiamata di funzione ricorsiva, gli argomenti della funzione e altri registri correlate sono inseriti nello stack, quindi non è necessario spazio aggiuntivo, d'altra parte, la profondità ricorsiva è correlata alla dimensione o altezza dell'albero, diciamo n, ha più senso di essere o (n)?

Grazie per qualsiasi spiegazioni qui!

Answer 1

Anche se lei ha ragione a dire che quella ricorsiva attuazione della algoritmo richiede O (n) di spazio a causa dello spazio di stack necessario, utilizza solo ricorsione di coda, che significa che può essere reimplementata all'uso O (1) spazio con un ciclo :

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

(Si noti che else deve essere aggiunto per mantenere inalterata la semantica.)

Answer 2

Questo algoritmo prevede ricorsione di coda. Nel contesto della tua domanda, lo stack frame del chiamante può essere riutilizzato dal chiamato. In altre parole, tutta la sequenza annidata di invocazioni funzione stanno per fare è passare il risultato come una brigata secchio. Di conseguenza, è effettivamente necessaria un'unica frame dello stack.

Per ulteriori lettura, vedi Tail chiamata a Wikipedia.