T(n) = (T(n-1) + n!) 的时间复杂度是多少？
What is the time complexity of T(n) = (T(n-1) + n!)?
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!)。
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!)。