shinigami1997
Senior Member
Thím có thể nghĩ tới quy hoạch động với 2 mảng 2 chiều
Chào mọi người, nay mình lập thread này để học tập về thuật toán, mình sẽ post các bài tập về thuật toán từ các nguồn trên mạng thường xuyên lên để mọi người cùng thảo luận. Thank you!
Bài 1:
View attachment 301611
k là gì đấy thím?Bài này mình thấy như này k biết đúng hay sai
1. Lấy max i,j
2. So sánh i,j để chạy vòng lặp
3. Nếu i<j độ phức tạp O(i) + O(j-i)^i
Nếu i>j độ phức tạp O(j) + O(j-i)^k
via theNEXTvoz for iPhone
Nói thật mình dốt toán lắm, chỉ nghĩ sao quote thôi ak.k là gì đấy thím?
Nếu tính O là cận trên của độ phức tạp thì vẫn là O(i*j) thôi mà thím
Độ phức tạp mọi người vẫn hay tính giá trị của vòng for mà.Nói thật mình dốt toán lắm, chỉ nghĩ sao quote thôi ak.
K ở đây là không - ý câu này là không biết đúng hay sai ấy.
Còn về tiệm cận thì mình k nghĩ ra đc là độ phức tạp i*j ở đâu.
Nếu thím loop i ( loop j) thì sẽ là i^j chứ nhỉ?
via theNEXTvoz for iPhone
Ủa, vậy thím nói độ phức tạp o(i*j) đc tính ntn vậy thím?Độ phức tạp mọi người vẫn hay tính giá trị của vòng for mà.
Còn ký hiệu O hay big-O là đại diện cho trường hợp worst case.
Thím có thể tham khảo ở đây: https://vnoi.info/wiki/translate/to...md#lưu-ý-khi-phân-tích-độ-phức-tạp-thuật-toán
Như thím nói là loop i ( loop j) đấy thôi.
Nhân chứ thím.Loop in loop phải là j^i chứ nhỉ?
via theNEXTvoz for iPhone
Độ phức tạp mọi người vẫn hay tính giá trị của vòng for mà.
Còn ký hiệu O hay big-O là đại diện cho trường hợp worst case.
Thím có thể tham khảo ở đây: https://vnoi.info/wiki/translate/to...md#lưu-ý-khi-phân-tích-độ-phức-tạp-thuật-toán
Ở bước 2 thì có thuật toán nào không ạ ? Hay chỉ for 2 mảng thôi bác ?Bước 1: Tính max i sao cho x^i < bound, max j sao cho y^j < bound. Dùng log là ra
Bước 2: Tính array A: x^0 -> x^i. Array B: y^0 -> y ^j
Bước 3: Tính tất cả các cặp của array A và B sao cho tổng nhỏ hơn bound
Cùng câu hỏi, cách mình là 1 lần for tới max(i,j)Ở bước 2 thì có thuật toán nào không ạ ? Hay chỉ for 2 mảng thôi bác ?