在分析我编写的一些代码时，我为它的运行时间提出了以下递归方程 -
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!) 是否正确，事实上，我很确定它不是。
如果我认为我做了一个错误的假设是正确的，我真的不确定如何实际求解上述递归方程，因为没有阶乘总和的公式......
任何指导将不胜感激。
谢谢！！！
由于您正在查看运行时，我认为O(n^2)这意味着该术语的操作数。在该假设下，n!可以及时计算O(n)( 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)算法。
我想到了。
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!)
问题在于：
T(n) = n*T(n-1) + n! + O(n^2)
是你混合了两种不同类型的术语。最后剩下的一切都+指一个数字；加号右边是O(n^2)表示所有函数的类，其渐近增长速度不超过n^2。
假设你的意思是：
T(n) = n*T(n-1) + n! + n^2
然后T(n) in O(n!)因为n!是总和中增长最快的项。（实际上，我不确定这n*T(n-1)不是更快的增长——我的组合不是那么强）。
展开递归项，递归“调用” ton*T(n-1)简化为某个函数，即，因此整个函数为。O((n!)!)O(n!)O(n!)
将递归项完全展开，它将是增长最快的项。有关正确扩展的各种建议，请参阅评论。
根据我对源代码的理解：
https://github.com/python/cpython/blob/main/Modules/mathmodule.c#L1982-L2032
如果不是更快，它最多只能是 O(n)。