shinigami1997
Senior Member
Thím có thể nghĩ tới quy hoạch động với 2 mảng 2 chiều
thảo luận [Học Tập] Topic thuật toán
- Người tạo chủ đề unknowpc90
- Ngày bắt đầu
Ngày Được Tự Do
Senior Member
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:
Bài 1:
Daedalus
Senior Member
Ý tưởng thuật toán:
- Với mỗi i, cho j lặp tăng dần đến khi x^i + y^j > bound thì chuyển sang giá trị i tiếp theo
- Độ phức tạp thuật toán: O(i*j)
Cài đặt bằng Go:
https://play.golang.org/p/O24uG_IEa4M
Sửa lần cuối:
boykun289
Junior Member
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
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
Daedalus
Senior Member
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
boykun289
Junior Member
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
Daedalus
Senior Member
Độ 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
boykun289
Junior Member
Daedalus
Senior Member
Như thím nói là loop i ( loop j) đấy thôi.
Với mỗi giá trị của i thì phải tính thêm j lần => i*j
Daedalus
Senior Member
Nhân chứ thím.
2 vòng lồng nhau với i = j = 5. Thì sẽ lặp i * j = 5 * 5 = 25 lần
Code thử ở đây ạ: https://play.golang.org/p/QOFe2AUTEaJ
realhaidinh
Senior Member
Để tối ưu bài này hơn thì e nghĩ là dùng thêm logarit nữa để giảm đpt
Big O không liên quan đến worst case đâu. Nó là chặn trên của độ phức tạp, có nghĩa là bất kỳ hàm f(n) nào tăng nhanh hơn g(n) thì đều là big-O của nó. Một thuật toán dùng n^2 phép tính thì gọi nó là O(n^3) hay O(2^n) cũng đều đúng cả.
Để chính xác thì nên dùng Theta, nhưng xác định Theta thường khó hơn nhiều.
Sent from Xiaomi Redmi 5A using vozFApp
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
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
Daedalus
Senior Member
Ở bước 2 thì có thuật toán nào không ạ ? Hay chỉ for 2 mảng thôi bác ?
Fzen
Đã tốn tiền
Cùng câu hỏi, cách mình là 1 lần for tới max(i,j)
Ngày Được Tự Do
Senior Member
Bài 2
Chủ đề tương tự
