我编写了一些代码,使用 Leibniz formula for determinants 计算给定 nxn 矩阵的行列式.
我试图用 O 表示法找出它的复杂性。
我认为应该是这样的:
O(n!) * O(n^2) + O(n) = O(n!*n^2)
或 O((n+2)!)
推理:我认为 O(n!)
是排列的复杂度。
O(n)
perm_parity 的复杂度,O(n^2)
是每次迭代 n 项的乘法。
这是我的代码:
def determinant_leibnitz(self):
assert self.dim()[0] == self.dim()[1] # O(1)
dim = self.dim()[0] # O(1)
det,mul = 0,1 # O(1)
for perm in permutations([num for num in range(dim)]):
for i in range(dim):
mul *= self[i,perm[i]] # O(1)
det += perm_parity(perm)*mul # O(n) ?
mul = 1 # O(1)
return det
计算中还使用了我编写的以下函数:
perm_parity:给定数字 0..n 按顺序排列为列表, 返回其奇偶校验(或符号):+1 表示偶校验; -1 表示奇数。
我认为 perm_parity 应该以 O(n^2)
运行(正确吗?)。
def perm_parity(lst):
parity = 1
lst = lst[:]
for i in range(0,len(lst) - 1):
if lst[i] != i:
parity *= -1
mn = argmin(lst[i:]) + i
lst[i],lst[mn] = lst[mn],lst[i]
return parity
argmin:返回列表中最小参数的索引。
我认为 argmin 应该以 O(n)
运行(正确吗?)
def argmin(lst):
return lst.index(min(lst))
和排列:返回给定列表的所有排列。 例如:输入:[1,2,3],输出[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1 , 2], [3, 2, 1]]。
我认为排列应该以 O(n!)
运行(正确吗?)
def permutations(lst):
if len(lst) <= 1:
return [lst]
templst = []
for i in range(len(lst)):
part = lst[:i] + lst[i+1:]
for j in permutations(part):
templst.append(lst[i:i+1] + j)
return templst
最佳答案
这是一个老问题,但仍然值得回答。
您正在寻找的复杂度是O((n+2)!)
。
这是因为 O(n!)
的复杂度是:
for perm in permutations([num for num in range(dim)])
O(n)
perm_parity
函数的复杂度。
O(n^2)
是每次迭代中相乘 n
项的复杂度。
这一切都给出O(n!)*O(n)*O(n^2)=O(n!n^2)=O((n+2)!)
(正如评论所述,在您的情况下,您甚至还会得到ϴ((n+2)!)
)
关于python - 莱布尼茨行列式公式复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16527834/