इस एल्गोरिदम की अंतरिक्ष जटिलता ओ (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 से छोटा है। समय जटिलता: हे (एन) अंतरिक्ष जटिलता: हे (1)

इस एल्गोरिथ्म पुनरावर्ती है, मुझे पता है कि जब एक पुनरावर्ती समारोह कॉल लागू, समारोह तर्क और अन्य संबंधित रजिस्टरों ढेर करने के लिए धक्का दिया है, इसलिए दूसरी जगह, अतिरिक्त जगह की आवश्यकता है, दूसरी तरफ, पुनरावर्ती गहराई पेड़ के आकार या ऊंचाई से संबंधित है, एन कहें, क्या यह ओ (एन) होने के लिए और अधिक समझ में आता है?

यहां किसी भी स्पष्टीकरण के लिए धन्यवाद!

Answer 1

यद्यपि आप यह कहने का अधिकार रखते हैं कि एल्गोरिदम के पुनरावर्ती कार्यान्वयन के लिए आवश्यक स्टैक स्पेस की वजह से ओ (एन) स्पेस की आवश्यकता होती है, यह केवल पूंछ रिकर्सन का उपयोग करती है, जिसका अर्थ है कि इसे ओ (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

इस एल्गोरिदम में पूंछ रिकर्सन शामिल है। आपके प्रश्न के संदर्भ में, कॉलर के ढेर फ्रेम को कैली द्वारा पुन: उपयोग किया जा सकता है। दूसरे शब्दों में, फ़ंक्शन इनवोकेशन के सभी नेस्टेड अनुक्रम एक बाल्टी ब्रिगेड की तरह परिणाम पास कर रहे हैं। नतीजतन, केवल एक ढेर फ्रेम वास्तव में आवश्यक है।

अधिक पढ़ने के लिए, विकिपीडिया पर Tail Call देखें।