如何计算递归矩阵行列式算法的时间与空间复杂度？

我需要计算这段用于递归求解矩阵行列式的Java代码的时间复杂度与空间复杂度：

public int determinant(int[][] m) {
    int n = m.length;
    if(n == 1) {
        return m[0][0];
    } else {
        int det = 0;
        for(int j = 0; j < n; j++) {
            det += Math.pow(-1, j) * m[0][j] * determinant(minor(m, 0, j));
        }
        return det;
    }
}

public int[][] minor(final int[][] m, final int i, final int j) {
    int n = m.length;
    int[][] minor = new int[n - 1][n - 1];
    int r = 0, s = 0;
    for(int k = 0; k < n; k++) {
        int[] row = m[k];
        if(k != i) {
            for(int l = 0; l < row.length; l++) {
                if(l != j) {
                    minor[r][s++] = row[l];
                }
            }
            r++;
            s = 0;
        }
    }
    return minor;
}

我的困惑 #

我自行计算的时间复杂度为输入规模(n²)与步骤数之和，空间复杂度为输入规模，得出O(n²)，但我认为这个结果不正确，也不理解为什么要除以n²。请问该如何计算该算法的时间与空间复杂度？

老师提示：确定算法关于n的操作数和内存消耗，再除以n²即可得到结果。

时间复杂度分析 #

这段代码采用拉普拉斯展开递归计算行列式，我们定义T(n)为计算n阶矩阵行列式的时间开销：

• 基准情况：当n=1时，T(1) = O(1)，直接返回唯一元素，无额外操作。
• 递归情况：对于n阶矩阵，要执行n次循环，每次循环包含三个关键操作：
  1. 符号计算Math.pow(-1,j)：属于常数时间O(1)；
  2. 生成余子式矩阵：minor方法会遍历原矩阵的所有n²个元素，筛选出非目标行/列的元素构建新矩阵，所以生成余子式的时间是O(n²)；
  3. 递归计算n-1阶行列式：开销为T(n-1)。

由此得到递归关系式：
T(n) = n * (O(n²) + T(n-1))，展开后为：

T(n) = n*T(n-1) + O(n³)

进一步展开递归式可以看到：

T(n) = n*(n-1)*T(n-2) + n*O((n-1)³) + O(n³)
= n*(n-1)*(n-2)*T(n-3) + n*(n-1)*O((n-2)³) + n*O((n-1)³) + O(n³)
...
= n! * T(1) + O(n³ + n*(n-1)³ + n*(n-1)*(n-2)³ + ... + n!*1³)

由于n!的增长速度远快于所有多项式项，整个时间复杂度的主导项是n!，因此最终时间复杂度为O(n!)。

关于老师提到的“除以n²”：这是引导你先拆解每一层递归的操作占比——比如每一层递归中，n个余子式的生成总操作数是n * n² = n³，但递归的总开销是各层操作的累加，而最终阶乘项的增长完全盖过多项式项，所以除以n²只是中间分析的步骤，不影响最终的阶乘级结论。

空间复杂度分析 #

空间复杂度需要考虑递归栈和临时生成的余子式矩阵：

• 递归调用栈：递归深度最多为n层（从n阶矩阵一直递归到1阶），每层栈只存储少量局部变量，开销为O(n)；
• 余子式矩阵：每次递归会生成一个(n-1)×(n-1)的矩阵，空间为O((n-1)²)。但由于递归是深度优先的——计算n阶行列式时，先生成第一个n-1阶余子式，递归计算它的行列式，此时会生成n-2阶余子式，直到递归到1阶才回溯释放空间，所以同一时间最多只存在一个当前递归层级的余子式矩阵，最大空间开销为O(n²)；
• 输入矩阵本身的空间是O(n²)，如果算法复杂度分析包含输入空间，总空间为O(n²)；如果只计算额外开销，额外空间也是O(n²)（递归栈+余子式）。

你之前得出O(n²)的错误在于，只关注了输入规模和单次操作的空间，忽略了时间复杂度中递归调用的阶乘级增长特性——每次递归要调用n次子问题，这才是时间复杂度的核心。

内容的提问来源于stack exchange，提问作者ZlyVlk