T(n)=T(n-1)+n(n-1)的渐进时间复杂度

根据递推式T(n)=T(n-1)+n(n-1)，可以得到T(n)=n(n-1)+T(n-1)=(n^2-n)+(n-1)^2+T(n-2)=...=n(n-1)+(n-1)^2+(n-2)^2+...+2^2+1^2+T(0)。因此，T(n)的时间复杂度为O(n^2)。这是因为T(n)的计算需要进行n次加法和n次乘法，因此随着n的增长，T(n)的执行时间将呈二次增长。

相关问题

T(n)=T(n-1)+n的渐进时间复杂度

这个递归式的渐进时间复杂度为O(n^2)。可以使用递归树来证明。递归树的每一层代表递归调用的一次，每一层的节点数为该层的n值，每个节点的代价为该层的n值。因此，递归树的总代价为每层代价之和。由于每层代价是上一层代价的n倍，因此总代价是一个等比数列，其和为O(n^2)。因此，该递归式的渐进时间复杂度为O(n^2)。

T(n)=T(n-1)+n∧2的渐进时间复杂度

根据递推式T(n)=T(n-1)+n^2，可以得到T(n)=T(n-2)+(n-1)^2+n^2，继续展开可以得到T(n)=T(n-3)+(n-2)^2+(n-1)^2+n^2，以此类推，直到T(1)=1^2。将所有式子相加可以得到T(n)=1^2+2^2+...+n^2，即T(n)=∑(i=1~n)i^2。根据求和公式∑(i=1~n)i^2=n(n+1)(2n+1)/6，所以T(n)=n(n+1)(2n+1)/6，即T(n)=O(n^3)。因此，T(n)=T(n-1)+n^2的渐进时间复杂度为O(n^3)。