Skip to main content
 首页 » 编程设计

python之莱布尼茨行列式复杂度

2024年11月01日9落叶

我编写了一些代码,使用 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)!))