查找递归函数的时间复杂度

Question

>我试图使用 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;
    }
}

Answer 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中最多只做一个递归调用，每次调用似乎都会将考虑的输入减少一个，并且你只在每一步做恒定量的处理，所以运行时应该只是 O（n）。

虽然这似乎很容易计算，但线性递归深度通常不是一个好主意（除了在识别和支持尾递归的语言中），因为堆栈大小通常比堆空间限制得多 - 您可能很容易遇到堆栈溢出异常。

所以通常情况下，一个人只会有两个嵌套循环（用于行和列），除非我错过了一些重要的东西。 代码中正在进行的处理。