Почему сложность этого алгоритма в пространстве равна O (1) - PullRequest
Новая
       16

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

5 голосов
/ 20 октября 2010

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

 /* 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, имеет ли смысл быть O (n)?

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

Ответы [ 2 ]

10 голосов
/ 20 октября 2010

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

Для получения дополнительной информации см. Tail Call в Википедии.

4 голосов
/ 20 октября 2010

Хотя вы и вправе сказать, что для рекурсивной реализации алгоритма требуется пространство O (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 необходимо добавить, чтобы сохранить семантику без изменений.)

...