algorithm - 递归算法的复杂度

Question

我有一个算法，想知道它的复杂度，但是有递归，不知道递归怎么算。我的代码是:

public boolean algorithm(int x, int y) {
    if (x == matrixHeight - 1 && matrix1[x][y] == '0') {
        return true;
    } else if (x == 1 && matrix1[x-1][y] == '0') {
        return true;
    } else if (y == matrixWidth - 1 && matrix2[x][y] == '0') {
        return true;
    } else if (y == 1 && matrix2[x][y-1] == '0') {
        return true;
    }
    if (matrix1[x-1][y] == '0' && tempMatrix[x-1][y] == '-'){
        path.push(new int[]{x-1, y});
        tempMatrix[x-1][y] = '+'
        if (!algorithm(x-1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y] == '0' && tempMatrix[x][y+1] == '-'){
        path.push(new int[]{x, y+1});
        tempMatrix[x][y+1] = '+';
        if (!algorithm(x, y+1)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix1[x][y] == '0' && tempMatrix[x+1][y] == '-'){
        path.push(new int[]{x+1, y});
        tempMatrix[x+1][y] = '+';
        if (!algorithm(x+1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y-1] == '0' && tempMatrix[x][y-1] == '-'){
        path.push(new int[]{x, y-1});
        tempMatrix[x][y-1] = '+';
        if (!algorithm(x, y-1)) {
            path.pop();
        } else {
            return true;
        }
    }
    return false;
}

• 在那里，x , y是矩阵中的坐标。
• matrix1和 matrix2是包含 '0' 的二维数组或 '1'
• tempMatrix是一个包含'+'或'-'的二维数组
• path是一个堆栈
• matrixHeight是matrix1.length
• matrixWidth是matrix[0].length
• N , M是矩阵的大小(常量)

注意:这是使用回溯的迷宫求解器。

Answer 1

对于递归，需要生成递归关系并求解。参见 http://en.wikipedia.org/wiki/Recurrence_relation .没有固定的方法来解决每个递归关系，甚至没有从算法中生成递归关系的方法。

一个例子是归并排序。考虑每次递归调用完成了多少工作。第一，有一个恒定的时间划分；然后进行两次递归调用；然后是线性时间合并。递归调用需要多少工作？好吧，每个人都做同样的事情，两次递归调用加上线性合并步骤。所以你需要一个表达式来表示树的深度和宽度。你知道对于 n 的输入大小，树的高度是 O(log(n))，并且在每一步总共完成 O(n) 合并工作，因此 O(n log(n)) 工作是总计完成。