Let function F is recursive and has running time of F(k) is T(k).
F(k) calls F(k-1) once, and does operations which run in O(n!)
F(0) is a base case, and it runs in constant time.
在我看来，
我以为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/