2

嘿，我无法使用我的代码计算拉普拉斯展开的复杂性：

def determinant_laplace(self, i=0):
    assert self.dim()[0] == self.dim()[1]
    if self.dim() == (1,1):
        return self[0,0]
    else:
        det = 0
        for col in range(self.dim()[1]):
            det += ((-1)**(col+i) *self[i,col]* self.minor(i,col).determinant_laplace())
        return det

为了更好地理解这一点，这是如何计算未成年人的（在我的代码中）：

def minor(self, i, j):
    t = self.dim()[0] # rows
    k = self.dim()[1] # columns
    assert isinstance(i, int) and isinstance(j, int) \
    and i < t and j < k
    newMat = Matrix(t-1,k-1) # new matrix will be with 1 less col and row
    for row in range(t):
        for col in range(k):
            if row < i and col < j:
                newMat[row,col] = self[row,col]
            elif row < i and col > j:
                newMat[row,col-1] = self[row,col]

            elif row > i and col < j:
                newMat[row-1,col] = self[row,col]

            elif row > i and col > j:
                newMat[row-1,col-1] = self[row,col]
    return newMat

如您所见，在 nxn 矩阵中创建次要的复杂度为 O(n^2)。

所以我被整体复杂性撕裂了 O(n!) 还是 O((n+1)!) 还是 O((n+2)!) ？

为什么是 O(n!) ：维基百科是这么说的，但我猜他们的实现是不同的，也许他们忽略了一些关于未成年人的计算。

为什么是 O((n+1))！: 递归序列是 n(n^2 + next(recursion_minor)..) = O(n*n!) = O((n+1)!)

为什么是 O((n+2)!) ：计算次要是 O(n^2)，我们计算 n! 其中我们得到 O(n^2)*O(n!)=O(n+2)！

我个人倾向于大胆的声明。

谢谢你的帮助。

4

2 回答 2

3

让f(n)是完成给定任何大小为 的determinant_laplace方阵所需的时间。nn

有n未成年人要计算。

对于每个未成年人，它需要

  • O((n-1)**2) = O(n**2)是时候创建未成年人了
  • 加上 f(n-1)计算determinant_laplace未成年人的时间

所以满足的递推不等式f为：

f(n) <= n(C*n**2 + f(n-1))

对于某些人C来说，对所有人来说n都比一些常数更大M。我不知道C和M 是什么，但我们可以将它们视为已知的、恒定的值。

考虑假设H(n)：

f(n) <= D * n * n!

D>0对于一些与 无关的常数n。

基本情况：对于n = 1, ..., M，我们可以找到一些非常大的常数D，使得

H(1), ..., H(M) are true, and D>C.

初步观察：请注意，n**3/n! < 1对于n >= 6，我们可以不失一般性假设M>6。

归纳步骤：采取一些n > M假设H(n-1)。

f(n) <= n(C*n**2 + f(n-1))          # by our recurrence inequality
     <= C*n**3 + n*D*(n-1)*(n-1)!   # by H(n-1)
      = C*n**3 + D*(n-1)*n!
     <= C*n! + D*(n-1)*n!           # since n**3 / n! < 1 and n > M > 6
      = (C+D*(n-1))*n! 
     <= D*n*n!                      # since D > C

也是如此H(n)。因此 f(n)在O(n*n!).

但是请注意，这是一个宽松的上限。本质上，相同的归纳证明可用于证明存在f(n)于O(n**(1/p)*n!)任何p = 1, 2, 3, ....

于 2013-05-20T18:47:58.920 回答
2

我认为这O(n+2)!是正确的答案。ij正如您所提到的，为 Matrix生成次要大小的复杂性n x n源自O(n^2)代码中的切片（o(k)在 python 中）。在递归结束时，您将得到 n! 未成年人（大小1 x 1）。所以我们来到了这里：

O(n^2) * O(n!) = O(n!(n+1)(n+2)) = O(n+2)!
于 2013-05-20T19:40:51.380 回答