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

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

• Phiên bản quét cạnh ở đây có độ phức tạp O(V * E): V-1 vòng, mỗi vòng quét tất cả E cạnh. Với heap nhị phân và danh sách kề, Prim chạy trong O((V + E) log V).

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

• O(V) cho mảng inTree (cộng với các cạnh đầu vào).

Tóm tắt:

• Prim mở rộng một cây, luôn thêm cạnh có trọng số nhỏ nhất nối ra ngoài cây, cho đến khi mọi đỉnh đều được đưa vào.
• Thuật toán tạo ra tổng trọng số nhỏ nhất giống như Kruskal, nhưng sử dụng chiến lược khác.