阶乘运行时间

Question

在分析我写的一些代码时，我得出了以下关于其运行时间的递归公式：

T(n) = n*T(n-1) + n！+ O(n^2)。

最初，我假设O((n+1)!) = O(n!)，因此我像这样解了方程-

T(n) = n！+ O(n!) + O(n^3) = O(n!)

推理，即使每一次递归都会产生另一个n！(不是(n-1)!，(n-2)！等)，它仍然只会达到n*n！= (n+1)！= O(n!)。最后一个参数是平方和。

但是，经过进一步的思考，我不确定我的假设O((n+1)!) = O(n!)是正确的，事实上，我很确定它不是。

如果我认为我做了一个错误的假设是正确的，我真的不确定如何实际解决上面的递归方程，因为没有阶乘和的公式……

任何指导都将不胜感激。

谢谢！

Answer 1

由于您关注的是运行时，我假设O(n^2)就是该术语上的操作数量。在此假设下，n!可以在O(n) time (1*2*3*...*n)中计算。因此，与O(n^2)术语相比，它可以被删除。然后，T(n-1)的计算时间大约为O((n-1)^2)，大致为O(n^2)。把所有这些放在一起，你就有了可以运行的东西

O(n^2) + O(n) + O(n^2)

从而产生O(n^2)算法。

Answer 2

我想通了。

T(n) = n*T(n-1) + n！+ O(n^2) = n*T(n-1) + n！= n*( (n-1)T(n-2) + (n-1)！)+ n！= n(n-1)T(n-2) + 2n！= ... = n！= n*n！= O(n*n!)

Answer 3

根据我对源代码的理解：

https://github.com/python/cpython/blob/main/Modules/mathmodule.c#L1982-L2032

它必须至多是O(n)，如果不是更快的话。