我正在Coursera学习算法课程,但是我卡在了这个问题上。我的任务是找到此代码的时间复杂度。
int sum = 0
for (int i = 1; i <= N*N; i = i*2)
{
for (int j = 0; j < i; j++)
sum++;
}
我在Eclipse中检查了这个问题,无论N的值是多少,sum语句执行的次数都小于N。
final value of sum:
for N=8 sum=3
for N=16 sum=7
for N=100000 sum=511
因此时间复杂度应该小于N,但给出的答案是N的平方,这可能怎么实现呢?
到目前为止,我所做的是:
第一个循环将运行log(N^2)次,因此第二个循环将执行1、2、3.. 2 logN次。