Почему пространство сложности этого алгоритма o (1)

Question

Привет всем: я прочитал алгоритм ниже, чтобы найти самый низкий общий предком из двух узлов в двоичном валке поиска.

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

Обратите внимание, что выше, функция предполагает, что N1 меньше, чем N2. Сложность времени: O (N) Космическая сложность: O (1)

Этот алгоритм рекурсивна, я знаю, что при вызове рекурсивного вызова функции функция аргументов и другие связанные регистры нажата в стек, поэтому необходима дополнительное пространство, с другой стороны, рекурсивная глубина связана с размером или высотой Дерево, скажем, это имеет больше смысла быть о (n)?

Спасибо за любые объяснения здесь!

Answer 1

Хотя вы правы говорят, что это рекурсивная реализация алгоритма требует (n) пространства из-за необходимого пространства стека, он использует только рекурсию хвоста, то есть его можно повторно использовать для использования пространства O (1) с петли:

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

(Обратите внимание, что else должен быть добавлен, чтобы сохранить семантику без изменений.)

Answer 2

Этот алгоритм включает рекурсию хвоста. В контексте вашего вопроса стек кадра абонента может быть повторно использован CALLEE. Другими словами, все вложенные последовательности вызовов функций будут делать, это пройти результат, как бригада ведра. Следовательно, только один кадр стека на самом деле требуется.

Для более для чтения см. Хвостовой звонок в Википедии.