Tại sao độ phức tạp của thuật toán này là O (1)

Question

Xin chào tất cả: tôi đọc thuật toán dưới đây để tìm tổ tiên chung thấp nhất của hai nút trong cây tìm kiếm nhị phân.

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

Lưu ý rằng trên chức năng giả định rằng n1 nhỏ hơn n2. Thời gian phức tạp: O (n) Không gian phức tạp: O (1)

thuật toán này là đệ quy, tôi biết rằng khi gọi một hàm gọi đệ quy, các đối số chức năng và thanh ghi liên quan khác được đẩy vào stack, vì vậy thêm không gian là cần thiết, mặt khác, độ sâu đệ quy có liên quan đến kích thước hoặc chiều cao của cây, nói n, nó có ý nghĩa hơn là O (n)?

Cảm ơn mọi giải thích tại đây!

Answer 1

Mặc dù bạn có quyền nói rằng việc triển khai thuật toán đòi hỏi không gian O (n) vì không gian ngăn cần thiết, nó chỉ sử dụng đệ quy đuôi, có nghĩa là nó có thể được thực hiện lại để sử dụng không gian O (1) với 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; 
    } 
} 

(lưu ý rằng else phải được thêm vào trong để giữ cho ngữ nghĩa không thay đổi.)

Answer 2

Thuật toán này liên quan đến đệ quy đuôi. Trong bối cảnh của câu hỏi của bạn, khung ngăn xếp của người gọi có thể được tái sử dụng bởi callee. Nói cách khác, tất cả các chuỗi lồng nhau của các lời gọi hàm sẽ làm là chuyển kết quả lên như một lữ đoàn. Do đó, chỉ cần một khung ngăn xếp thực sự được yêu cầu.

Để đọc thêm, hãy xem Tail Call tại Wikipedia.