algorithm - 求解运行时间

Question

请有人给我一个关于如何解决运行时间的方向：T(n) = nT(n-1) + O(n^2)？

我知道 T(n) = nT(n-1) => T(n) = O(n!) 但是如何用额外的 O(n^2) 解决它？

提前致谢！

Answer 1

在家工作？无论如何，这取决于。如果您正在寻找 Big-O 时间，则 O(n^2) 不会添加任何内容。O(N!) 消耗 O(N^2)，对于 N 的几乎所有值。或者更确切地说，对于 N > 3 的值，N! > N^2。你也可以这样展示。N！+ 16 > N^2 对于所有 N。

或者，您可以像这样计算组合计算时间

T(N) = N! + N^3.

T(N) = nT(n-1) + n^2
T(N) = (n - 1)T(n-2) + n^2 + (n-1)^2
T(N) = (n-2)(n-1)T(n-2) + n^2 + (n-1)^2 + (n-2)^2
T(N part 1) = 1 * 2 * 3 ... * n = n!
T(N part 2) = 1 + 4 + 9 ... + n^2 = (1/3)n3 + (1/2)n2 + (1/6)n

T(N) = n! + (1/3)n^3 + (1/2)n^2 + (1/6)n
T(N) = n! + n^3
T(N) = n! 

答案是三个底线之一，具体取决于我们想要的关于 big-O 的粒度级别。我喜欢中间那个，因为它承认多项式复杂性，同时显然留下了 n！作为主要关注点，而不会使答案过于复杂。