math - T(n) = (T(n-1) + n!) 的时间复杂度是多少？

在我的诚实看来，
我认为 T(n) = T(0) + (1! + 2! + ... + n!) 所以
这将是 T(n) <= (n! + n! + ... + n!) for n >=1 。
因此 O((n+1)!) 。
但我不能确定这是否足够。
分析够了吗？有什么方法可以测试吗？
(这个算法不太实用，但出于好奇。)

最佳答案

阶乘总和没有很好的封闭形式(exact answer 很乱)。

但是，我们可以用归纳法来证明 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!)。

关于math - T(n) = (T(n-1) + n!) 的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37076214/