nashwade
Senior Member
Bác lưu 20000 cái queue tương ứng do mỗi độ cao, rồi duyệt queue từ nhỏ đến lớn.
thảo luận [Học Tập] Topic thuật toán
- Người tạo chủ đề unknowpc90
- Ngày bắt đầu
thuyduong2007
Member
T không nghĩ là cách này work. Vì thím bỏ toàn bộ độ cao vào sau đó duyệt để lấy từ nhỏ đến lớn. => cái ô đầu tiên mà thím lấy được nó có độ cao nhỏ nhất nhưng vị trí của nó có thể nằm ở giữa chứ k phải ngoài biên => sai ngay từ bước đầu tiên rồi.
Kân team
Member
duyệt từng ô trong mảng mxn xem ô nào có 4 ô bên cạnh cao hơn thì cộng thêm vào
làm tối đa 20k lần như vậy
O(mnh) ~ 200x200x20000 = 800tr < 1 tỏi được mà
à cũng khó phải loang ra nữa ko xét từng ô riêng lẻ được
làm cái mảng 20k cũng được mà đâu cần tới heap gì ở đây
làm tối đa 20k lần như vậy
O(mnh) ~ 200x200x20000 = 800tr < 1 tỏi được mà
à cũng khó phải loang ra nữa ko xét từng ô riêng lẻ được
làm cái mảng 20k cũng được mà đâu cần tới heap gì ở đây
Sửa lần cuối:
nashwade
Senior Member
thuyduong2007
Member
Ok, t hiểu ý thím rồi. Thay vì pop, push trong heap (O(logn)) thì cách này đơn giản là chỉ cần access vào trong cái mảng O(1). Nhưng khi search để tìm ra cái min tiếp theo thì phải dùng linear search đúng k? vậy thì độ phức tạp phải là O(m*n*20000) mới đúng chứ nhỉ. Đâu phải O(m*n + 20000) đâu. Hay t đang hiểu sai cách của thím?
Sửa lần cuối:
nashwade
Senior Member
Trong code của thím biến curMax chỉ có tăng lên nên để tìm cái min tiếp theo mình cứ pop từ cái queue ở độ cao curMax ra hết, nếu không còn thì lại tiếp tục tăng curMax lên. Độ phức tạp của 1 lần pop có thể lên tới O(20000) nhưng độ phức tạp của cả process cũng chỉ là O(m*n + 20000) vì mỗi phần tử chỉ được pop ra O(1) lần.Ok, t hiểu ý thím rồi. Thay vì pop, push trong heap (O(logn)) thì cách này đơn giản là chỉ cần access vào trong cái mảng O(1). Nhưng khi search để tìm ra cái min tiếp theo thì phải dùng linear search đúng k? vậy thì độ phức tạp phải là O(m*n*20000) mới đúng chứ nhỉ. Đâu phải O(m*n + 20000) đâu. Hay t đang hiểu sai cách của thím?
thuyduong2007
Member
Ok, Mình đã hiểu. Cảm ơn đã giải thích nhé.
.Tóm lại là ntn: giả sử phần tử lớn nhất trong matrix có giá trị là k, khi đó sẽ cần m*n lần push O(1) và k lần pop O(1). Nên => dpt là O(m*n + k) đúng k?
cách tính dpt ntn ổn chưa? Mời các cao nhân nhận xét.
. @_Gia_Cat_Luong_
_Gia_Cat_Luong_
Senior Member
Chuẩn đét luôn, mình cũng mới biết cách này, khá hay đấy chứ. Thank thím @nashwade đã chia sẻ.Ok, Mình đã hiểu. Cảm ơn đã giải thích nhé.
Tóm lại là ntn: giả sử phần tử lớn nhất trong matrix có giá trị là k, khi đó sẽ cần m*n lần push O(1) và k lần pop O(1). Nên => dpt là O(m*n + k) đúng k?
cách tính dpt ntn ổn chưa? Mời các cao nhân nhận xét.
dev_thatvidieu
Junior Member
Chào các thím, thật ngại quá khi phải lập topic làm voz thấy em đang tạo rác cho box này. Mong các thím thông cảm nhưng vã quá ạ...Mong min mod ngang quá thông cảm.
Chẳng là em đang cày lại giải thuật. Đến mục phân tích độ phức tạp của thuật toán. Em đang bị bí quá do trường em ngày xưa không có dạy về cái này (Không có tài liệu về nó), thầy có thể giảng qua trong 1-2 tiết mà chắc ngày ấy em cúp tiết nên next nó luôn, giờ ôn lại thấy vã quá.
Phương pháp của em bây giờ để phân tích độ phức tạp của thuật toán chỉ đơn giản là dò xem thuật toán ấy nó thực thi (n) bước theo input thế nào rồi khái quát lên một đa thức.
Ví dụ như thuật toán đơn giản nhất thế này:
___________________
___________________
=> được khái quát : T (n) = 3 + 3n2 + 2n + 1 => big O = O(n^2)
Cái bí nhất của em chính là với các thuật toán đơn giản thì có thể khái quát nên đa thức rồi nhẩm ra độ phức tạp. Còn với những thuật toán phức tập hơn em có thể phải mất cả tiếng để ra được độ phức tạp. Thậm chí là kẻ bảng các kiểu vẫn chậm, có cái sai bét.
Nên em mong vozer thông thái chỉ bảo và share kinh nghiệm ạ. Em cảm ơn
Chẳng là em đang cày lại giải thuật. Đến mục phân tích độ phức tạp của thuật toán. Em đang bị bí quá do trường em ngày xưa không có dạy về cái này (Không có tài liệu về nó), thầy có thể giảng qua trong 1-2 tiết mà chắc ngày ấy em cúp tiết nên next nó luôn, giờ ôn lại thấy vã quá.
Phương pháp của em bây giờ để phân tích độ phức tạp của thuật toán chỉ đơn giản là dò xem thuật toán ấy nó thực thi (n) bước theo input thế nào rồi khái quát lên một đa thức.
Ví dụ như thuật toán đơn giản nhất thế này:
___________________
JavaScript:
for i in range(n):
for j in range(n):
x = i * i
y = j * j
z = i * j
for k in range(n):
w = a*k + 45
v = b*b=> được khái quát : T (n) = 3 + 3n2 + 2n + 1 => big O = O(n^2)
Cái bí nhất của em chính là với các thuật toán đơn giản thì có thể khái quát nên đa thức rồi nhẩm ra độ phức tạp. Còn với những thuật toán phức tập hơn em có thể phải mất cả tiếng để ra được độ phức tạp. Thậm chí là kẻ bảng các kiểu vẫn chậm, có cái sai bét.
Nên em mong vozer thông thái chỉ bảo và share kinh nghiệm ạ. Em cảm ơn
KimSoHyunGoddness
Member
Vào cái topic học thuật toán đi bạn ơi.
Có 2 trường phái.
1 trường phái tính chính xác tới từng cái, 1 trường phái là ko cần, tính ~ Big O là được.
Tôi nghĩ với trường hợp của bạn, ko cần đào sâu mấy cái này. Lên leetcode luyện, hiểu dc cách tính O(N) O(N2) các kiểu là được rồi, ko cần chi tiết như này. Sau này có thời gian đào sâu cũng được.
Giờ đâm vô mấy cái này dễ nản lắm. Kiếm cái project nào thực tế mà làm.
1 trường phái tính chính xác tới từng cái, 1 trường phái là ko cần, tính ~ Big O là được.
Tôi nghĩ với trường hợp của bạn, ko cần đào sâu mấy cái này. Lên leetcode luyện, hiểu dc cách tính O(N) O(N2) các kiểu là được rồi, ko cần chi tiết như này. Sau này có thời gian đào sâu cũng được.
Giờ đâm vô mấy cái này dễ nản lắm. Kiếm cái project nào thực tế mà làm.
dev_thatvidieu
Junior Member
Cảm ơn các thím đã khai trí cho em nhé. Chưa đi làm thực tế về lập trình nên cày đám lý thuyết này đúng là khá phức tạp.
KimSoHyunGoddness
Member
Hôm nay tới 2 bài này. Cái đứng hình luôn. Em có biết linked list biểu diễn ntn đâu mà làm. Huhu
kunguyenqt
Junior Member
Thì đọc tìm hiểu thôi bác. LinkedList là kiến thức cơ bản, trước sau gì cũng phải học hếtXem tệp đính kèm 728107
Hôm nay tới 2 bài này. Cái đứng hình luôn. Em có biết linked list biểu diễn ntn đâu mà làm. Huhu
KimSoHyunGoddness
Member
Nhưng linked list trong JS em ko nhìn thsây được hình dạng nó ntn nên khó hình dung quáThì đọc tìm hiểu thôi bác. LinkedList là kiến thức cơ bản, trước sau gì cũng phải học hết
Coffe_Bên_Lề
Senior Member
Thím nên thử qua linked list single cho đơn giản rồi tiến đến các dạng khác, linked list như array thôi nhưng nó linh động hơn nhiều do không bị giới bởi bộ nhớ
htss
Senior Member
Linked list khác array nhé, array truy xuất O(1), linked list truy xuất O(n).
còn array ko bị giới hạn bởi bộ nhớ là dynamic array (mảng động) hay vector trong c++.
eraganxs
Member
Viết cái hàm in nội dung nó ra.
Chủ đề tương tự
