2

我编写了一些代码，使用Leibniz 行列式公式计算给定 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
4

1 回答 1

2

这是一个老问题，但仍然值得回答。

您正在寻找的复杂性是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)!)）

于 2016-01-25T18:28:40.610 回答