Phân tích phức tạp thời gian sử dụng big-o

Question

Sau khi sửa đổi, chúng tôi kết luận rằng độ phức tạp thời gian thực sự là O (2^n)

Câu hỏi là độ phức tạp về thời gian? Có phải O (2^n) hay không?

Lý do tôi tin rằng điều này là do vòng lặp for được coi là được chạy n lần. Sau đó vòng lặp lồng nhau chạy 2^n thời gian. Vòng lặp thứ hai trong khi chạy 2^n thời gian.

Algorithm subsetsGenerator(T)  
Input: A set T of n elements  
Output: All the subsets of T stored in a queue Q {  

create an empty queue Q;  
create an empty stack S;  
let a1, a2, …, an be all the elements in T;  
S.push({}); // Push the empty subset into the stack  
S.push({a1})   
for (each element ai in T-{a1})   
{ 
    while (S is not empty)     
    { 
x=S.pop;      
Q.enqueue(x);       
x=x ∪ { ai };      
Q.enqueue(x);      
    }    

if (ai is not the last element)     
    while (Q is not empty)      
    { 
    x=Q.dequeue();       
    S.push(x);       
    }   
}  
} 

Chỉnh sửa: Nếu bạn muốn tôi phân tích phân tích, nhận xét dưới đây.

Answer 1

Đối với các phần tử T của n, tổng số tập con là 2^n. Nếu bạn muốn giữ tất cả các tập con đó trong Q, độ phức tạp của thời gian ít nhất là O (2^n).

---

Thực ra tôi nghĩ O (2^n) là câu trả lời.

Nếu tôi hiểu thuật toán của bạn một cách chính xác, bạn đang cố gắng làm cho mỗi phần tử a_i trong T, lấy tất cả mọi thứ trong S, đặt nó trở lại S hai lần - một lần không có a_i và một lần với a_i.

Do đó tổng thời gian phức tạp là (1 + 2 + 4 + ... + 2^n) lần C, C là thời gian để bật, enqueue, dequeue và push, là O (1). Thuật ngữ trên bằng 2^(n + 1) -1 vẫn là O (2^n).