递归算法的复杂度

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 is matrix1.length
• matrixWidth is matrix[0].length
• N, M为矩阵的大小(常数)

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

Answer 1

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

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

Answer 2

它看起来像一个深度优先的迷宫求解器，如果你能退出迷宫，返回true，否则返回false。复杂度为O(lines * columns)，因为在最坏的情况下，访问每个单元格的次数是恒定的。

1 1 1 1
1 0 0 1
0 0 0 1
1 1 1 1

从(1,1)开始。你的算法将向上，向后走，向右走，再向上，向后走，再向右，向后走，然后向下等等。对于像这样构造的迷宫，看起来你的算法将花费大量时间来解决它们。

事实上，大多数递归(更准确地说是深度优先)方法将花费很长时间，因为总是有可能强迫它们执行最大数量的步骤。

查看Lee算法以获得更好的方法。

Answer 3

对于这个算法的复杂性，实际上有一个非常简单的分析。

每次调用algorithm都会对algorithm进行0到4次递归调用，并执行一些固定数量的其他工作。所以，如果我们可以限定algorithm被调用的次数，那么我们就知道复杂度了。现在，请注意，在之前，每次调用algorithm(除了第一个)，您将tempMatrix的一个元素从'-'更改为'+'。因此，算法的调用次数以tempMatrix的大小为限，复杂度为O(matrixWidth * matrixHeight)。

另一种方法(使用更有意义的变量名会更明显)是简单地注意到您正在对x-y网格进行深度优先搜索。所以每个"广场"都会被访问一次。