2

行列式のライプニッツ公式を使用して、特定の 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 に答える