Độ phức tạp thời gian của thuật toán Prim

Question

Tôi đã xem xét Wikipedia entry cho thuật toán của Prim và tôi nhận thấy rằng độ phức tạp thời gian của nó với ma trận kề là O (V^2) và độ phức tạp của nó với danh sách heap và adjacency là O (E lg (V)) trong đó E là số cạnh và V là số đỉnh trong biểu đồ.

Vì thuật toán của Prim được sử dụng trong biểu đồ đậm đặc hơn, E có thể tiếp cận V^2, nhưng khi đó, độ phức tạp thời gian với một heap trở thành O (V^2 lg (V)) lớn hơn O (V^2). Rõ ràng, một đống sẽ cải thiện hiệu suất trên chỉ tìm kiếm mảng, nhưng độ phức tạp thời gian nói khác đi.

Thuật toán thực sự chậm với cải tiến như thế nào?

Answer 1

Mặc dù heap giúp bạn không tìm kiếm qua mảng, nó làm chậm phần "cập nhật" của thuật toán: cập nhật mảng là O (1), trong khi cập nhật heap là O (log (N)).

Về bản chất, bạn trao đổi tốc độ trong một phần của thuật toán cho tốc độ khác.

Không có vấn đề gì, bạn sẽ phải tìm kiếm N lần. Tuy nhiên, trong biểu đồ dày đặc, bạn sẽ cần phải cập nhật rất nhiều (~ V^2) và trong biểu đồ thưa thớt, bạn không cần.

Ví dụ khác ngoài đầu tôi đang tìm kiếm các phần tử trong một mảng. Nếu bạn chỉ làm điều đó một lần, tìm kiếm tuyến tính là tốt nhất - nhưng nếu bạn thực hiện nhiều truy vấn, tốt hơn nên sắp xếp nó và sử dụng tìm kiếm nhị phân mỗi lần.

Answer 2

Tôi nghĩ bạn đã đọc sai ở một mức độ nào đó. Đối với các đồ thị dày đặc, bài viết nói về việc sử dụng các vùng Fibonacci với độ phức tạp thời gian O (E + V log V), tốt hơn đáng kể.

Answer 3

Từ Giới thiệu về thuật toán (Carmen)

Time = Θ (V) · T (TRÍCH-MIN) + Θ (E) · T (GIẢM-KEY)

 
        T(EXTRACT-MIN) T(DECREASE-KEY) Total 

1. array   O(V)    O(1)    O(V^2) 
2. binary heap  O(lgV)   O(lgV)   O(E lgV) 
3. Fibonacci heap O(lgV)   O(1)    O(E + VlgV) 

Sử dụng các cấu trúc dữ liệu khác nhau gây ra những phức tạp về thời gian khác nhau.