T(n)=T(n-1)+n∧2的时间复杂度
时间: 2023-12-26 18:05:54 浏览: 65
根据递归树法,可以画出递归树,对于一个节点,节点的值为非函数项,再将式中每一个函数项向下迭代,式中有n个函数项,递归树就是n叉树,且有n层,把每一行所有节点的和写在右边,如下图所示:
```
n^2
/ | \
(n-1)^2 (n-2)^2 ... 1^2
/ | \
(n-2)^2 ... 1^2
/ | \
...
```
可以看出,每一层的节点数都是上一层的1/3,所以总节点数为n^2+n^2/3+n^2/9+...=3n^2,因此时间复杂度为Θ(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)。
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)的执行时间将呈二次增长。