用协因式法求矩阵行列式的时间复杂度

Question

尝试使用在网络上找到的方法来获得矩阵的行列式。但是我不确定这个方法的时间复杂度，因为程序中使用了递归。我意识到有

1. one for loop循环遍历第一行元素
2. 处理较小矩阵的递归函数。

这是否意味着程序的最坏时间复杂度是O(N^2)?

# python program to find
# determinant of matrix.

# defining a function to get the
# minor matrix after excluding
# i-th row and j-th column.


def getcofactor(m, i, j):
return [row[: j] + row[j+1:] for row in (m[: i] + m[i+1:])]

# defining the function to
# calculate determinant value
# of given matrix a.


def determinantOfMatrix(mat):

# if given matrix is of order
# 2*2 then simply return det
# value by cross multiplying
# elements of matrix.
if(len(mat) == 2):
value = mat[0][0] * mat[1][1] - mat[1][0] * mat[0][1]
return value

# initialize Sum to zero
Sum = 0

# loop to traverse each column
# of matrix a.
for current_column in range(len(mat)):

# calculating the sign corresponding
# to co-factor of that sub matrix.
sign = (-1) ** (current_column)

# calling the function recursily to
# get determinant value of
# sub matrix obtained.
sub_det = determinantOfMatrix(getcofactor(mat, 0, current_column))

# adding the calculated determinant
# value of particular column
# matrix to total Sum.
Sum += (sign * mat[0][current_column] * sub_det)

# returning the final Sum
return Sum


# Driver code
if __name__ == '__main__':

# declaring the matrix.
mat = [[1, 0, 2, -1],
[3, 0, 0, 5],
[2, 1, 4, -3],
[1, 0, 5, 0]]

# printing determinant value
# by function call
print('Determinant of the matrix is :', determinantOfMatrix(mat))

# This code is contributed by Amit Mangal.

Answer 1

使用协因子方法计算n × n矩阵的行列式需要计算n个矩阵的行列式，每个矩阵的大小为n-1，然后进行大约2n次运算(加法和乘法)。因此，代价是T(n) = nT(n-1)+cn。如果你画递归树或者用其他方法来解这个递归，你会得到T(n) = O(n!)这比O(n^2)大得多