mã trên giả dụ cho việc sinh xâu nhị phân có độ dài n, em muốn hỏi là dùng cách này hay là đệ quy quay lui nhanh hơn ạ ? Em cảm ơn rat nhiu :<
Độ phức tạp sinh xâu nhị phân dùng for và bitwise so với quay lui
2 thuật toán đều có độ phức tạp là O(2^n) thôi bạn.
Cách này nhanh hơn chứ. Đệ quy độ phức tập 2^n. Còn cái này độ phức tạp có O(N^2)
vd n = 1000 thì bitwise mất đâu đó 1e6 phép tính trong khi đệ quy 2^1000 thì có mà toang.
1 << n là 2^n mà bạn 
2 Likes
Nên dùng như trong hình, còn đại quy nhiều dễ bị tràn stack
1 Like
đây bác ui. Nó dịch từng bit 1 mà. Độ lớn không đáng kể thì mình tính O(n^2) thui. Em học lâu lâu r ko nhớ rõ lắm.
Uhm, vấn đề là vòng lặp đầu tiên chạy từ 0 tới 2^n, vòng thứ 2 chạy từ 0 tới n. Độ phức tạp là O(n * 2^n) cậu ạ.
Nếu cả 2 vòng đều chạy từ 0 tới n thì cậu đúng, độ phức tạp là O(n^2).
Phép dịch bit thì đúng là chỉ O(1) thôi.
5 Likes
= )) oh mình nhầm thật xin tiếp thu.
1 Like
Khi thi ở trường thì có 1 số bài mình đệ quy không AC nhưng khi dùng bitwise thì lại được. Với nó cũng ngắn hơn và khá dễ nhớ (cá nhân mình cảm giác vậy)
Mình có tham khảo thêm chat gpt nữa bạn thử tham khảo xem
1 Like
Đệ quy còn tốn bộ nhớ (lưu trạng thái đệ quy vào stack, đệ quy càng sâu thì càng tốn bộ nhớ) nên không phải ngẫu nhiên mà một số bài cần khử đệ quy.
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?