递归关系的时间复杂度 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²)。

从 1 到 n 的所有自然数的乘积叫什么？

Answer 2

只有最后的复杂度是错误的，你最终得到了 O(n!)。

递归关系必须是T(n) = T(n-1)+n才能得到O(n^2)的复杂度。