cho em hỏi đoạn code sau độ phức tạp của thuật toán như thế nào vậy ạ. Mọi người có thể giải thích chi tiết giúp em hiểu với được không ạ.
void in(int k){
cout<<"Cach "<<count++<<" : "<<n<<" = ";
for(int i=1;i<k;i++)
cout << x[i]<<" + ";
cout << x[k]<<endl;
}
void Try(int i){
for(int j=x[i-1] ; j<=(n-t[i-1])/2 ; j++){
x[i]=j;
t[i]=t[i-1]+j;
Try(i+1);
}
x[i]=n-t[i-1];
in(i);
}
Đoạn code này có chức năng là gì vậy bạn?
Đề bài là : Với số tự nhiên n cho trước tính xem có bao nhiêu cách biểu diễn n thành tổng của 1 hay nhiều số tự nhiên khác ( không tính đến thứ tự của các số hạng, ví dụ 3 = 2 + 1 = 1 + 2 coi như là một cách biểu diễn). mình dùng đệ thuật toán quy lui để làm.
Không có khái niệm độ phức tạp của đoạn code …
Chỉ có khái niệm độ phức tạp của 1 giải pháp/solution 1 giải thuật để xử lý 1 vấn đề cụ thề với không gian dữ liệu cụ thể (ở đây là số tự nhiên N)
Đoạn code của em vẫn thiếu đoạn em dùng hàm try như thế nào mới đầy đủ bức tranh để đánh giá giải pháp có độ phức tạp bao nhiêu.
Về cơ bản idea thì anh có thể nói thế này : Nếu em chỉ cần duyệt hết các trường hợp có thể 1 lần duy nhất xong rồi tìm ra kết quả thì nó là O(N) hay gọi la tuyến tính.
Dựa trên ý tưởng đó nếu e cần duyệt tới 2 lần tất cả các trường hợp thì cứ thế nhân lên…
Đọc thêm sách về độ phức tạp em nhé
Bài này sao mà SV giải được.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?