Độ phức tạp thời gian và không gian

Độ phức tạp thời gian:

• Sắp xếp E cạnh có độ phức tạp O(E log E); mỗi thao tác union-find gần như có độ phức tạp O(1) nhờ nén đường đi, vì vậy thuật toán Kruskal cổ điển có độ phức tạp O(E log E). Phiên bản chọn cạnh nhỏ nhất mà chúng ta xây dựng ở đây có độ phức tạp O(E²), phù hợp với đồ thị nhỏ.

Độ phức tạp không gian:

• O(V) cho mảng parent (cộng thêm các cạnh đầu vào).

Tóm tắt:

• Kruskal xây dựng cây khung nhỏ nhất bằng cách thêm cạnh không tạo chu trình có trọng số nhỏ nhất ở mỗi bước, dùng union-find để kiểm tra chu trình.
• Tất cả cây khung nhỏ nhất đều có cùng tổng trọng số, vì vậy đáp án là duy nhất.