递归关系的时间复杂度T（n）= T（n-1）* n

Question

我需要以下递归关系的帮助。

T（1）= 1

T（n）= T（n-1）* n

这是我尝试过的。我想我可能已经把替换部分弄乱了，但是请再次让我看看我的时间复杂度是否正确。

T(n) = T(n-1)*n               T(n-1) = T(n-2)*n-1
T(n) = [T(n-2)*(n-1)]*n
T(n) = T(n-2)*(n-1)*n
T(n) = [T(n-3)*n-2]*(n-1)*n
T(n) = T(n-3)*(n-2)*(n-1)*n
...
...
...
T(n) = T(n-k)*(n-(k-1))*(n-(k-2))...*(n-1)*(n)

Assuming n-k=0, n=k

T(n) = T(n-n)*(n-n+1)*(n-n+2)...*(n-1)*(n)
T(n) = T(0)*(1)*(2)...*(n-1)*n

O(n^2)

现在，我不确定我所做的工作是否正确，但会有所帮助。

Answer 1

非常接近！您已正确识别出复杂度为

n *（n-1）*（n-2）* ... * 3 * 2 * 1。

但是，不是O（n ²）。如果您^添加而不是相乘，则将为O（n 2）。

您如何称呼所有自然数从1到n（包括1和n）的乘积？

Answer 2

只有最后的复杂性是错误的，您最终得到O（n！）。

为了获得O（n ^ 2）作为复杂度，递归关系必须为T（n）= T（n-1）+ n。