algorithm - T(n) = T(n-1) + O(n * n!) 的渐近复杂度是多少？

Question

T(n) = T(n-1) + O(n * n!) 的渐近复杂度是多少？严格的上限就足够了。我正在尝试计算一个非常复杂的递归算法的时间复杂度来查找字谜，最终我想出了这个公式(希望它是正确的)。您可以假设算法在达到 T(1) 时停止。

编辑:T(n) = T(n-1) + O(n * n!) 当然等于 O(n*n!) + O((n-1)*(n-1)!) + ... + O(1) 但我不知道该怎么做。

Answer 1

要严格了解正在发生的事情，请注意

n * n! = (n + 1) * n! - n! = (n + 1)! - n!

因此原函数可以重写为:

T(n) = T(n-1) + c * ((n + 1)! - n!)  where c is a constant from the O(f(n)) notation

如果展开 T(n-1) 等，您会看到阶乘抵消了 finally

T(n) = T(0) + c * ((n + 1)! - 0!)

因此，如果 T(0) 是常数且有限，

T(n) = O((n + 1)!)