In che modo l'unione trova l'algoritmo quadratico?

Question

In questa implementazione dell'algoritmo Ricerca rapida, Constructor accetta i passi N così come union().

L'istruttore detto che union è troppo costoso in quanto richiede N^2 per elaborare sequenza di Nunion comandi su N oggetti, Come può union quadratico quando si accede agli elementi dell'array uno alla volta?

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

Ogni invocazione del union metodo richiede di eseguire iterazioni sul id matrice, che prende O(n) tempo. Se invochi il metodo union il metodo n, il tempo richiesto è n*O(n) = O(n^2).

È possibile migliorare la complessità temporale del metodo su O(1), aumentando la complessità temporale del metodo connesso, probabilmente O(log n), ma questa operazione è una sola volta. Credo che il tuo libro di testo lo spieghi nei dettagli.

Answer 2

Union operazione per veloce è quadratica O(n^2) per n operazioni, perché ogni operazione richiede O(n) tempo, come è facile notare nel ciclo for all'interno union(int p, int q)

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

Si noti che l'algoritmo si chiama rapida Trova, poiché ogni operazione di ricerca (connected(int p, int q)) richiede un tempo costante. Tuttavia, per questo algoritmo si finisce per pagare l'operazione , come indicato nella domanda.

C'è un altro algoritmo Quick Union, che migliora il tempo per l'operazione union. Ma allora find non rimane O(1) (ma migliore del tempo lineare).