Warum der Raum Komplexität dieses Algorithmus ist O (1)

Question

Hallo alle: Ich lese den Algorithmus unter die kleinsten 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);
}    

Beachten Sie, dass obige Funktion geht davon aus, dass n1 kleiner als n2 ist. Zeitkomplexität: O (n) Speicherkomplexität: O (1)

Dieser Algorithmus rekursiv ist, 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 Platz benötigt wird, auf der anderen Seite wird die rekursive Tiefe auf die Größe bezogen oder Höhe des Baumes, sagt n, macht es mehr Sinn, O (n) sein?

Vielen Dank für alle Erklärungen hier!

Answer 1

Auch wenn Sie Recht zu sagen, dass die rekursive Implementierung des Algorithmus O (n) Platz benötigt wegen der Stapelspeicher benötigt, verwendet es nur Endrekursion, dh es ist mit einer Schleife zur Verwendung von O (1) Raum neu implementiert werden kann :

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 in werden hinzugefügt unverändert die Semantik zu halten.)

Answer 2

Dieser Algorithmus beinhaltet Endrekursion. Im Zusammenhang mit der Frage, der Stapelrahmen des Anrufers kann durch die Angerufenen wieder verwendet werden. Mit anderen Worten, alle der verschachtelte Sequenz von Funktionsaufrufen tun wird, ist das Ergebnis nach oben wie eine Eimerkette übergeben. Folglich wird nur ein Stapelrahmen tatsächlich erforderlich ist.

Für weitere Lesung finden Sie unter Endaufruf an der Wikipedia.