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) 等，你会看到阶乘最终抵消了给定

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

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

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

Answer 2

它是 O(n*n!)。后面的每一项都是由前项支配的低阶多项式。