求一列语句的时间复杂度怎么求？

Question

1)
i=1;
s=0;
while(i<n)
{
s=s+10*i;
i++;
}

2)

i=1;
j=0;
wile(i+j<>n)
if(i>j)j++;
else i++

3)

y=1;
while(y*y<=n) y=y+1;

4)
i=n;
while(i>0)i=i/2;

5)

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
s++;

6)

for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;

这些题怎么做，大神能告诉我简单的分析方法吗，感谢

Answer 1

给你个列子，这个很简单的
(1) for(i=1;i<=n;i++) //循环了n*n次，当然是O(n^2)
for(j=1;j<=n;j++)
s++;
(2) for(i=1;i<=n;i++)//循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数
for(j=i;j<=n;j++) 的，所以也是O(n^2)
s++;
(3) for(i=1;i<=n;i++)//循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)
for(j=1;j<=i;j++)
s++;
(4) i=1;k=0;
while(i<=n-1){
k+=10*i;
i++;
}//循环了n-1≈n次，所以是O(n)