So sánh độ phức tạp của thuật giải BFS sử dụng danh sách kề và ma trận

Một phần của câu 2 trong môn thuật giải của Nhóm 2:

Cách biểu diễn đồ thị có ảnh hưởng lớn đến thời gian thực hiện.
Trong trường hợp biểu diễn bằng danh sách kề cả hai thuật toán đều có :
O(n+m)=O(max(n,m)) ( n, m tương ứng là số đỉnh và số cạnh của đồ thị)
Nếu biểu diễn bằng ma trận kề thì độ phức tạp sẽ là O(n+n2)=O(n2)
Nếu biểu diễn theo danh sách cạnh thì việc duyệt những đỉnh kề với đỉnh u thì phải duyệt qua toàn bộ danh sách cạnh, O(n.m).
Như vậy, độ phức tạp trong trường hợp biểu diễn bằng danh sách kề là tốt nhất

khoai_dao đã viết:Một phần của câu 2 trong môn thuật giải của Nhóm 2:

Cách biểu diễn đồ thị có ảnh hưởng lớn đến thời gian thực hiện.
Trong trường hợp biểu diễn bằng danh sách kề cả hai thuật toán đều có :
O(n+m)=O(max(n,m)) ( n, m tương ứng là số đỉnh và số cạnh của đồ thị)
Nếu biểu diễn bằng ma trận kề thì độ phức tạp sẽ là O(n+n2)=O(n2)
Nếu biểu diễn theo danh sách cạnh thì việc duyệt những đỉnh kề với đỉnh u thì phải duyệt qua toàn bộ danh sách cạnh, O(n.m).
Như vậy, độ phức tạp trong trường hợp biểu diễn bằng danh sách kề là tốt nhất

Không thể khẳng định độ phức tạp trong trường hợp biểu diễn bằng danh sách kề là tốt nhất. Mối cách biểu diễn đều có ưu - khuyết điểm khác nhau.
Nếu xét về chi phí bộ nhớ thì đúng là biểu diễn bằng đồ thị bằng danh sách kề tốt hơn so với ma trận kề, vì chi phí bộ nhớ cho cách biểu diễn bằng danh sách là O(|V|+2|E|) và cho ma trận kề là O(V2), với V là số đỉnh, E là số cạnh của đồ thị.
Nhưng xét về chi phí về thời gian xử lý thì độ phức tạp của cách biểu diễn bằng ma trận kề lại tốt hơn, vì chi phí về thời gian xử lý của ma trận kề chỉ là O(1), còn của danh sách kề là O(V) đơn vị thời gian.