recursion - 行列式递归算法的复杂度计算

Question

我编写了一个基于拉普拉斯展开式的算法来计算 n x n 矩阵的行列式:

我得到下面的递推关系:T(n) = n(n² + T(n-1))

我在维基百科上读到，这应该产生结果 T(n) = O(n!)，但我不知道如何证明这一点(尽管很直观)。

Answer 1

公式是正确的，但你的递归关系不正确。您不需要n² ，因为您不必保存或生成子矩阵。

M<sub>ij</sub>是 (n-1) x (n-1) 的决定因素子矩阵。所以你必须计算n n的决定因素不同的矩阵。所以正确的递推关系是T(n) = n⋅T(n-1) + 2n-1 。这简化为

T(n) = n ⋅ T(n-1) + 2n-1
     = n ⋅ (n-1) ⋅ T(n-2) + n ⋅ (n-1)
     = n ⋅ ( (n-1) ⋅ ( (n-2) ⋅ (...) + n-3 ) + n-2 ) + n-1
     = 2n-1 + n ⋅ (2(n-1)-1) + n ⋅ (n-1) ⋅ (2(n-2)-1) + ... + n!
     < 2 ⋅ n + 2 ⋅ n ⋅ (n-1) + 2 ⋅ n ⋅ (n-1) ⋅ (n-2) + ... + 2 ⋅ n! + n!
     = 2 ⋅ (n + n ⋅ (n-1) + ... + n!/2) + 3 ⋅ n!
     < 2 ⋅ (n!/(n-1)! + n!/(n-2)! + ... + n!/2!) + 3 ⋅ n!

由于 2⋅n!/k! ≤ n!/(k-1)!对于所有人k ≥ 2 ，我们得到

  n!/(n-1)! + n!/(n-2)! + n!/(n-3)! + ... + n!/2!
≤ n!/(n-2)! + n!/(n-2)! + n!/(n-3)! + ... + n!/2!
≤ n!/(n-3)! + n!/(n-3)! + ... + n!/2!
≤ n!/(n-4)! + ... + n!/2!
≤ ...
≤ n!/2! + n!/2!
≤ n!

所以

T(n) = n ⋅ T(n-1) + 2n-1
     < 2 ⋅ (n!/(n-1)! + n!/(n-2)! + ... + n!/2!) + 3 ⋅ n!
     ≤ 2 ⋅ n! + 3 ⋅ n!
     = 5 ⋅ n!
     = O(n!)

所以你的算法运行在 O(n!)