General forums

Forum Description Discussions
News forum
General news and announcements
 0

Learning forums

Week Forum Description Discussions
Java 2: Analiza e Algoritmeve. Algoritmet Gjej-Bashkim (Union-Find) Shembull i zgjidhur

Trego me një kundërshembull se ky implementim i funksionit union() për algoritmin quick-find (gjetje-e-shpejtë), nuk është i saktë.

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

 1
Shembull i zgjidhur

Cili është rendi i rritjes në funksion të N-së për kodin e mëposhtëm:

int sum = 0;
for (int i = 1; i <= 5*N*N; i = i + 4)
    sum++;

 1
quick-union wrong implementation

Trego me një kundërshembull se ky implementim i funksionit union() për algoritmin quick-find (gjetje-e-shpejtë), nuk është i saktë.

public void union(int p, int q) {
   if (connected(p, q)) return;
   for (int i = 0; i < id.length; i++)
      if (id[i] == id[p]) id[i] = id[q];
   count--;
}

 1