2016-04-22 15 views
0

私はこの関数の全体的な複雑さをBig-Oh表記法を使って調べようとしています。関数checkElements()はpercolates()の内部にある再帰的に呼び出されます。感謝再帰関数の時間複雑さの発見

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; 
    } 

} 
+0

再帰はどこですか? –

+0

メソッドcheckElements() –

答えて

1

あなたは

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; 
} 

への再帰呼び出しを変更する場合、これは従うことが容易にあなたがcheckElementsにのみ、最大1つの再帰呼び出しを行っているかもしれない、とそれぞれの呼び出しを考慮入力を減らすように見えます1つだけで、あなたは各ステップでの処理量はnstantなので、ランタイムは単にO(n)にする必要があります。

これは計算が簡単であるように見えますが、通常、スタックサイズはヒープスペースよりもはるかに制限されているため、線形再帰の深さは良い考えではありません(末尾再帰を認識しサポートする言語以外では簡単です)スタックオーバーフロー例外が発生します。

私は何か重要なwrtを逃していない限り、典型的には、2つのネストされたループ(行と列用)があります。あなたのコードで処理が続けられます。

+0

同じコードの下限か大きなシータを見つける方法はありますか? –

+0

私はそれがすべて同じ境界だと思う - ランタイムを短くするような特別な入力がないように見える - すべてのセルはどんな場合でも横断するようだ。 –

関連する問題