我认为功能是：T（n）=n（T（n-1））+n^2

O(n^2)是单个非终止递归调用的时间复杂度，但不是总的时间复杂度。
每个调用test(n)，如果它没有命中递归的Base case，则创建递归调用的n + 1分支。
例如，如果n = 2。递归调用树将是：

t(2)
           /    |   \
          /     |    \
      t(1)     t(1)   t(1)
      /  \     /  \    /  \
  t(0) t(0) t(0) t(0) t(0) t(0)

所以调用test(2)会导致9递归调用，如果我们调用test(3)，它会派生40递归调用。
基本上我们有：

(n) * (n + 1 - 1) * (n + 1 - 2) * (n + 1 - 3) * ... until `n` doesn't turn to 1

这类似于阶乘，如果我们忽略+1，那么它大概是n!个递归调用，每个递归调用的时间复杂度都是O(n^2)
因此，总体时间复杂度可以表示为：

O(n^2 * n!)

这是一个相当复杂的函数。让我们从下往上看，也许我们能看到一些东西。

T(0) = 1
T(1) = 2 * (2 + T(0)) = 2 * (2 + 1) = 2 * 3 = 6
T(2) = 3 * (3 + T(1)) = 3 * (3 + 6) = 2 * 9 = 27
T(3) = 4 * (4 + T(2)) = 4 * (4 + 27) = 4 * 31 = 124

如果我们以不同的方式展开

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

如果我们打开T（n）的圆括号

T(n) = (n+1)^2 + (n+1)n*(n + T(n-1)) = (n+1)^2 + (n+1)n^2 + (n+1)n(n-1)*((n-1) + T(n-1)) = ... 
= (n+1)^2 + (n+1)n^2 + ... + (n+1)n(n-1)...2^2 + (n+1)! = Sum[iProduct[j,{j,i,n}],{i,2,n}] + (n+1)!

（我用wolfram alpha做加法，我希望这是正确的）
从最后的和中我们可以看到，和中最大的元素是(n+1)!，其他的元素都比较小，所以我们可以忽略它们，而且+1也是没有意义的，所以我们也可以忽略它，最终的结果是你的递归函数是o(n!)。
如果有人问为什么是n+1，那是因为循环条件是i<=n而不是i < n。而且我已经很多年没有做过这种类型的分析了，我希望我没有犯任何重大错误。

将操作替换为所需的时间，可以建立以下重复：

T(0) = C0
T(n) =
    Σ{i=0..n}
        Σ{j=0..n}
            C1
        +
        T(n-1)
    + C2

这可以重写

T(n) = (n+1).((n+1).C1 + T(n-1)) + C2 = (n+1).T(n-1) + (n+1)².C1 + C2

这个递推式的精确解是一个技术性很强的问题，通过求解齐次方程，我们得到解C.(n+1)!，通过改变系数，我们设置

T(n) = (n+1)!.U(n)

然后

(n+1)!.U(n) = (n+1).n!.U(n-1) + C1.(n+1)² + C2

或

U(n) = U(n-1) + C1/(n-2)! + 2C1/(n-1)! + C2/(n+1)!

我们认识到e的截断级数，它很快收敛到一个常数

T(n) ~ C(n+1)! = O((n+1)!)

您的T（n）公式不正确，应为：

T(n) = n * (T (n-1) + n)

原因是你有n次迭代，每次迭代（这就是乘积的来源），你都要做一次递归，所以基本上你会得到：

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

其中T（0）= 1基本上给出了你的定义，所以现在通过一些重新排序和乘法，你会得到：

T (n) = n^2 + n*((n-1)^2) + n*(n-1)*((n-2)^2) + ... + n*(n-1)*(n-2)*(n-3)*...*(n-(n-3))*(2^2) + (2 * n!)

最后2 * n！原因是T（1）= 2，通过乘法得到系数n！。（该过程基本上从T（n-1）开始，将方程乘以n并将其加到T的方程中（n）你去掉T（n-1）。但是你现在有TT方程中的（n-2）（n）所以重复这个过程）所以我认为（但不确定）时间复杂度将是n！而不是n^2，我希望这是有帮助的。