莱布尼兹行列式公式的复杂度 [英] Leibniz determinant formula complexity

问题描述

我写了一些代码，使用行列式的莱布尼兹公式来计算给定nxn矩阵的行列式

I wrote some code that calculates the determinant of a given nxn matrix using Leibniz formula for determinants.

我试图弄清楚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个项的乘法.

I am trying to figure out it's complexity in O-notation. I think it should be something like: O(n!) * O(n^2) + O(n) = O(n!*n^2) or O((n+2)!) Reasoning: I think O(n!) is the complexity of permutations. and O(n) the complexity of perm_parity, and O(n^2) is the multiplication of n items each iteration.

这是我的代码:

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

我编写的以下函数也用于计算:

The following functions that I wrote are also used in the calculation:

perm_parity:给定数字0..n的排列顺序，作为列表，返回其奇偶校验(或符号):+1表示偶数奇偶校验；-1为奇数.

perm_parity: Given a permutation of the digits 0..n in order as a list, returns its parity (or sign): +1 for even parity; -1 for odd.

我认为perm_parity应该在 O(n ^ 2)上运行(对吗?).

I think perm_parity should run at O(n^2) (is that correct?).

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)上运行(对吗?)

argmin: returns the index of minimal argument in a list. I think that argmin should run at O(n) (is that correct?)

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]].

and permutation: returns all the permutations of a given list. e.g: input: [1,2,3], output [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

我认为排列应该以 O(n！)(正确吗?)

I think that permutations should run at O(n!) (is that correct?)

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

推荐答案

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

This is an old question but still deserves an answer.

您要查找的复杂度是 O((n + 2)！) .
这是因为 O(n！) 的复杂性:
用于排列的烫发([num表示范围(dim)中的num])
O(n) perm_parity 函数的复杂性.
O(n ^ 2) 是每次迭代中将 n 个项目相乘的复杂性.
这全部给出 O(n！)* O(n)* O(n ^ 2)= O(n！n ^ 2)= O((n + 2)！)

The complexity you are looking for is O((n+2)!).
This is since O(n!) is the complexity of this:
for perm in permutations([num for num in range(dim)])
O(n) the complexity of theperm_parity function.
O(n^2) is the complexity of multiplying n items in each iteration.
This all gives O(n!)*O(n)*O(n^2)=O(n!n^2)=O((n+2)!)

(正如评论所述，在您的情况下，您甚至还会得到 ϴ((n + 2)！) )

(And as the comment stated, in your case you also even get ϴ((n+2)!))

这篇关于莱布尼兹行列式公式的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！