Warum die Raumkomplexität dieses Algorithmus ist O (1)

Question

Hallo alle: Ich lese den Algorithmus unten, um den niedrigsten gemeinsamen Vorfahren von zwei Knoten in einem binären Suchbaum zu finden.

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

anzumerken, dass vorstehende Funktion wird davon ausgegangen, dass n1 kleiner als n2 ist. Zeitkomplexität: O (n) Speicherkomplexität: O (1)

dieser Algorithmus ist rekursiv, ich weiß, dass, wenn ein rekursive Funktionsaufruf aufgerufen wird, wird die Funktionsargumente und andere damit zusammenhängende Register auf den Stapel geschoben werden, so zusätzlicher Raum wird benötigt, andererseits hängt die rekursive Tiefe mit der Größe oder Höhe des Baumes zusammen, n, macht es mehr Sinn, O (n) zu sein?

Danke für irgendwelche Erklärungen hier!

Answer 1

Obwohl Sie zu Recht sagen, dass diese rekursive Implementierung des Algorithmus O (n) space wegen des benötigten Stack-Speicherplatzes erfordert, wird nur die Tail-Rekursion verwendet, was bedeutet, dass sie mit einem O (1) -Raum wieder verwendet werden kann Loop:

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

(Beachten Sie, dass else hinzugefügt werden muss, in der Semantik unverändert zu halten.)

Answer 2

Dieser Algorithmus beinhaltet Tail-Rekursion. Im Rahmen Ihrer Frage kann der Stack-Frame des Aufrufers vom Angerufenen wiederverwendet werden. Mit anderen Worten, die gesamte verschachtelte Folge von Funktionsaufrufen wird das Ergebnis wie eine Eimerkette weiterleiten. Folglich wird tatsächlich nur ein Stapelrahmen benötigt.

Für mehr lesen, siehe Tail Call in der Wikipedia.