某算法时间复杂度函数的递推方程如 T(n)=T(n−1)+nT(n) = T(n - 1) + nT(n)=T(n−1)+n 其中 n∈N+n\in\mathbb{N_+}n∈N+ 且 T(0)=1T(0)=1T(0)=1，求时间复杂度。
某算法时间复杂度函数的递推方程如 T(n)=T(n−1)+nT(n) = T(n - 1) + nT(n)=T(n−1)+n
其中 n∈N+n\in\mathbb{N_+}n∈N+ 且 T(0)=1T(0)=1T(0)=1，求时间复杂度。
用硬算可以算出来是 O(n2)O(n^2)O(n2)：
T(n)=T(n−1)+n=T(n−2)+2n−1=T(n−3)+3n−3=⋯⋯=T(0)+n2−(n−1)n2=O(n2)\begin{aligned}T(n)&=T(n-1)+n\\&=T(n-2)+2n-1\\&=T(n-3)+3n-3\\&=\cdots\cdots\\&=T(0)+n^2-\dfrac{(n-1)n}{2}\\&=O(n^2)\end{aligned}T(n)=T(n−1)+n=T(n−2)+2n−1=T(n−3)+3n−3=⋯⋯=T(0)+n2−2(n−1)n=O(n2)
这边想问一下有没有大佬能用主定理算一遍，因为考场上很可能还是要用主定理的/qq
