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

Question

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

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

noti che sopra presuppone che la funzione n1 è minore di n2. 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, in modo è necessario ulteriore spazio, d'altra parte, la profondità ricorsiva è correlata alla dimensione o all'altezza dell'albero, ad esempio, ha più senso essere O (n)?

Grazie per qualsiasi spiegazione qui!

Answer 1

Sebbene sia corretto affermare che l'implementazione ricorsiva dell'algoritmo richiede O (n) spazio a causa dello spazio di stack necessario, utilizza solo ricorsione in coda, il che significa che può essere reimplementato per utilizzare lo spazio O (1) 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 la ricorsione della coda. Nel contesto della tua domanda, la cornice dello stack del chiamante può essere riutilizzata dal destinatario. In altre parole, tutta la sequenza annidata delle invocazioni delle funzioni sta per passare il risultato come una brigata di secchio. Di conseguenza, solo un frame dello stack è effettivamente richiesto.

Per ulteriori letture, vedere Tail Call su Wikipedia.