DFS o(b*m)
BFS o(b^(d+1))
M.n giải thích giúp mình, mình chưa hiểu về độ phức tạp bộ nhớ lắm.
b: hệ số phân nhánh tối đa của cây
d: độ sâu lời giải có chi phí thấp nhất
m: độ sâu cây
Độ phức tạp bộ nhớ của thuật toán BFS và DFS
Vì BFS vừa duyệt tầng d vừa đưa tầng d+1 vào bộ nhớ luôn.
DFS thì thực ra có thể làm O(m) thôi, tuy nhiên bạn lại phải “đánh số thứ tự” rất khó, nên cứ nạp hết trạng thái vào thôi.
6 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?