如何计算时间复杂度的计算比如说i=-1;s=0;while(s<n){i=i+2;s=s++i;}为什么它的时间复杂度是根号n;

2025-04-13 02:22:55
推荐回答(3个)
回答1:

s=s++i? 少了一个加号或者多了一个加号吧
若s=s+i 你会发现 s0=0+1;s1=1+3;s2=4+5;s3=9+7 发现s0=1;s1=4;s2=9;s3=16 为0,1,2,3,4的平方 当n->无穷的时候 while至多运行根号n的下限次,所以复杂度是根号n

回答2:

这是因为s=-1+1+3+5+...+i=n时,n∝(i^2),也就是 i∝√n

回答3:

时 i > m
否则就没完了