T(n) = (T(n-1) + n!) 的时间复杂度是什么？

Question

假设函数F是递归的，运行时间为F(k)就是T(k)。 F(k)调用了一次F(k-1)，并执行一些需要O(n!)的操作。 F(0)是基本情况，它运行的时间是常数。

在我看来，我认为T(n) = T(0) + (1! + 2! + ... + n!)，所以当n>=1时， 它应该小于等于(n! + n! + ... + n!)。 因此时间复杂度为O((n+1)!)。

但我不能确信这是否足够，是否有任何方法可以测试？（这个算法不是很实用，只是好奇。）

- kidkkr

Answer 1

没有一个漂亮的封闭形式可以用来计算阶乘的和（确切答案很复杂）。

然而，我们可以使用归纳法证明 0! + 1! + 2! + ... + n! ≤ 2n!：

• 基本情况：0! ≤ 2 · 0!，0! + 1! ≤ 2 · 1!，0! + 1! + 2! ≤ 2 · 2!
• 归纳：0! + 1! + ... + k! + (k+1)! ≤ 2k! + (k+1)! ≤ (k+1)k! + (k+1)! = 2(k+1)!

因此，您的递归从上到下被限制在2n!，从下到上被限制在n!，这意味着您可以得到最紧密的边界，即该递归解决为Θ(n!)。

- templatetypedef

---

这不是 Θ((n+1)!) 吗？ - user3235832

@willywonka_dailyblah 我相信我所概述的证明表明0！+1！+...+n！<= 2n！，这给出了更紧密的界限Theta（n！）。或者我错了吗？ - templatetypedef

我同意归纳步骤。这非常令人愉悦。 - kidkkr

哦，抱歉我明白了，你是正确的。 - user3235832

@kaya3 为了澄清，证明将总和从上面限制为2(n!)，从下面限制为n!，这就是Theta(n!)的来源。我同意这不等同于Theta((n+1)!)，而这个答案背后的想法是证明OP最初的限制并不紧密。 - templatetypedef

抱歉，我的错误，我误读了你的回答。对不起！ - kaya3