python - 阶乘运行时间

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) 时间内计算 (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) 算法。