一个行列式递归算法的复杂度计算

Question

我已经编写了一个算法来计算基于拉普拉斯展开的n x n矩阵行列式。我得到了以下递归关系：T(n) = n(n² + T(n-1))。在维基百科上，我读到这应该得出结果T(n) = O(n!)，但我不知道如何证明它（尽管这是直观的）。

- user2375340

---

如果右边没有出现 T，则它不是一个递归关系。 - Scott Hunter

抱歉，应该是 T 而不是 F。我已经更正了。 - user2375340

你写的代码不是O(n!)的。T(n)=nT(n-1)=O(n!)。你的复杂度比较高。 - SomeWittyUsername

@icepack 尝试构建表示递归关系的函数（非常简单 - 大约3行代码）。然后，计算大量i（我认为即使i = 5也足够了）的f（i + 1）/ f（i）。您会注意到f（i + 1）/ f（i）= i + 1。我非常确定它意味着f（n）= O（n！）。请注意，我并不声称f（n）等于n！但渐近地“表现”像n！。 - user2375340

你确定这个公式是正确的吗？求和似乎只针对 i 和 j 中的一个，但两个变量都被使用了。 - templatetypedef

Answer 1

公式是正确的，但您的递归关系不对。您不需要n²，因为您不必保存或生成子矩阵。 Mij 是一个(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!

由于对于所有的 k ≥ 2，都有 2⋅n!/k! ≤ n!/(k-1)!，因此我们得到：

  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!

And so

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!)。

- AbcAeffchen