我是分析时间复杂度的新手。有人可以帮助我解决以下算法的时间复杂度吗?
public void test(int n)
{
for(int i=1;i<=n;i=i+2)
{
for(int j=1;j<=i;j++)
{}
}
}
外循环将运行n / 2次。内循环将运行(1 + 3 + 5 + 7 + 9 ... n)次。内环的时间复杂度是多少,如何计算这种算术级数的总和?]
假设n为奇数。然后n = 2k + 1大约k。现在
1 + 3 + … + n
= 1 + 3 + … + 2k+1
= (1 + 3 + … + 2k + 1) + (1 + 1 + … + 1) - (1 + 1 + … + 1)
= (1 + 1) + (3 + 1) + … + (2k + 1 + 1) - (1 + 1 + … + 1)
= 2 + 4 + … + 2k+2 - (1 + 1 + … + 1)
= 2(1 + 2 + … + k+1) - (1 + 1 + … + 1)
= 2(k+1)(k+2)/2 - (k+1)
= k^2 + 3k + 2 - k - 1
= k^2 + 2k + 1
= (k+1)^2
= (n+1)^2/4
我们可以测试几个词...
n f(n) Series Sum
1 1 1 = 1
3 4 1 + 3 = 4
5 9 1 + 3 + 5 = 9
7 16 1 + 4 + 5 + 7 = 16
看起来好像已签出。