Công đoàn tìm thuật toán bậc hai như thế nào?

Question

Trong quá trình thực hiện thuật toán Tìm nhanh này, Constructor mất N các bước như vậy union().

Các giảng viên nói rằng union là quá đắt vì nó mất N^2 để xử lý chuỗi các Nunion lệnh trên N đối tượng, Làm thế nào có thể union được bậc hai khi nó truy cập các phần tử mảng cùng một lúc?

public class QuickFind 
{ 
    private int[] id; 

    public QuickFind(int N) { 
     id = new int[N]; 
     for (int i=0; i<N; i++) { 
      id[i] = i; 
     } 
    } 

    public boolean connected(int p, int q) { 
     return id[p] == id[q]; 
    } 

    public void union(int p, int q) { 
     int pid = id[p]; 
     int qid = id[q]; 

     for (int i=0; i<id.length; i++) 
      if (id[i] == pid) 
       id[i] = qid; 
    } 
} 

Answer 1

Mỗi gọi của union phương pháp đòi hỏi bạn lặp qua các id mảng, trong đó có O(n) thời gian. Nếu bạn gọi phương thức unionn lần, thì thời gian bắt buộc là n*O(n) = O(n^2).

Bạn có thể cải thiện độ phức tạp của phương pháp union thành O(1), bằng cách làm cho độ phức tạp của phương pháp được kết nối cao hơn, có lẽ là O(log n), nhưng đây chỉ là một thao tác một lần. Tôi tin rằng cuốn sách văn bản của bạn giải thích chi tiết này.

Answer 2

Union hoạt động cho nhanh Tìm là bậc hai O(n^2) cho n hoạt động, bởi vì mỗi hoạt động có O(n) thời gian, như là dễ dàng để thông báo trong vòng lặp for bên union(int p, int q)

for (int i=0; i<id.length; i++) 

Chú ý rằng các thuật toán được gọi là nhanh Tìm, vì mỗi hoạt động tìm kiếm (connected(int p, int q)) mất thời gian không đổi. Tuy nhiên đối với thuật toán này, bạn sẽ chỉ phải trả tiền trong hoạt động union, như được đề cập trong câu hỏi của bạn.

Có một thuật toán khác Quick Union, giúp cải thiện thời gian cho hoạt động union. Nhưng sau đó find không còn là O(1) (nhưng tốt hơn thời gian tuyến tính).