Zeitkomplexität der rekursiven Funktion finden

Question

Ich versuche, die gesamte Zeitkomplexität dieser Funktion mit Big-Oh-Notation zu finden, Die Funktion checkElements() wird rekursiv aufgerufen, die innerhalb der Percolates() liegt viel

geschätzt

public static boolean percolates(boolean[][] open) { 
    size = open.length; 
    uf = new WeightedQuickUnionUF((size * size) + 2); 
    for (int i = 0; i < open.length; i++) {//connect all top row elements to virtual top node. 
     uf.union(0, i); 
    } 

    for (int j = 0; j < open.length; j++) {//connect all bottom row elements to bottom virtual node 
     uf.union((size * size) + 1, (size * size) - j); 

    } 
    int row = 0; // current row of grid 
    int column = 0;// current column of grid 
    int ufid = 1; // current id of union find array 
    checkElements(column, row, open, ufid); 
    boolean systemPerculates = uf.connected(0, (size * size) + 1); 
    System.out.println("Does the system percoloates :" + systemPerculates); 
    return systemPerculates; 
} 

//search elements in the grid 
public static void checkElements(int column, int row, boolean open[][], int ufid) { 
    if (open[row][column]) { 
     if (column - 1 >= 0 && open[row][column - 1]) { //check adjacent left 
      uf.union(ufid, ufid - 1); 

     } 
     if (column + 1 < size && open[row][column + 1]) {//check adjacent right 
      uf.union(ufid, ufid + 1); 

     } 
     if (row - 1 >= 0 && open[row - 1][column]) {//check adjacent top 
      uf.union(ufid, ufid - size); 

     } 
     if (row + 1 < size && open[row + 1][column]) {//check adjacent bottom 
      uf.union(ufid, ufid + size); 

     } 
    } 
    if (column + 1 < size) {  //go to next column 
     ufid++; 
     column++; 
     checkElements(column, row, open, ufid); 
    } else if (column + 1 == size && row + 1 < open.length) { //go to next row 
     ufid++; 
     row++; 
     column = 0; 
     checkElements(column, row, open, ufid); 
    } else { 
     return; 
    } 

} 

Answer 1

Dies könnte einfacher sein, zu folgen, wenn Sie die rekursive Aufrufe zu

if (column + 1 < size) {  //go to next column 
    checkElements(column + 1, row, open, ufid + 1); 
} else if (column + 1 == size && row + 1 < open.length) { //go to next row 
    checkElements(0, row + 1, open, ufid + 1); 
} else { 
    return; 
} 

nur

Sie tun in checkElements bis zu einem rekursiven Aufruf zu ändern, und jeder Anruf scheint die als Eingang zu reduzieren um eins, und du machst nur eine Co nstant Menge der Verarbeitung bei jedem Schritt, so sollte die Laufzeit nur O (n) sein.

Während dies einfach zu berechnen scheint, ist lineare Rekursionstiefe normalerweise keine gute Idee (anders als in Sprachen, die Tail-Rekursion erkennen und unterstützen), da die Stackgröße normalerweise wesentlich begrenzter als der Heapspeicher ist in eine Stapelüberlaufausnahme laufen.

Also normalerweise hätte man nur zwei verschachtelte Schleifen (für Zeilen und Spalten), außer ich vermisse etwas Wichtiges. Die Verarbeitung läuft in Ihrem Code ab.