嘿,我无法使用我的代码计算拉普拉斯展开的复杂性:
def determinant_laplace(self, i=0):
assert self.dim()[0] == self.dim()[1]
if self.dim() == (1,1):
return self[0,0]
else:
det = 0
for col in range(self.dim()[1]):
det += ((-1)**(col+i) *self[i,col]* self.minor(i,col).determinant_laplace())
return det
为了更好地理解这一点,这是如何计算未成年人的(在我的代码中):
def minor(self, i, j):
t = self.dim()[0] # rows
k = self.dim()[1] # columns
assert isinstance(i, int) and isinstance(j, int) \
and i < t and j < k
newMat = Matrix(t-1,k-1) # new matrix will be with 1 less col and row
for row in range(t):
for col in range(k):
if row < i and col < j:
newMat[row,col] = self[row,col]
elif row < i and col > j:
newMat[row,col-1] = self[row,col]
elif row > i and col < j:
newMat[row-1,col] = self[row,col]
elif row > i and col > j:
newMat[row-1,col-1] = self[row,col]
return newMat
如您所见,在 nxn 矩阵中创建次要的复杂度为 O(n^2)。
所以我被整体复杂性撕裂了 O(n!) 还是 O((n+1)!) 还是 O((n+2)!) ?
为什么是 O(n!) :维基百科是这么说的,但我猜他们的实现是不同的,也许他们忽略了一些关于未成年人的计算。
为什么是 O((n+1))!: 递归序列是 n(n^2 + next(recursion_minor)..) = O(n*n!) = O((n+1)!)
为什么是 O((n+2)!) :计算次要是 O(n^2),我们计算 n! 其中我们得到 O(n^2)*O(n!)=O(n+2)!
我个人倾向于大胆的声明。
谢谢你的帮助。