题目

试分析下面各算法的时间复杂度。（1）x=90;y=100; while(y>0) if(x>100) (x=x-10;y--;) else x++;（2）for(i=0;i<n;i++) for(j=0; j<m; j++) a[i][i]=0;（3）s=0; for(i=0;i<n;i++) for(j=0;j<n;j++) s+=B[i][i]; sum=s;（4）i=1; while(i<=n) i=i3;（5）x=0; for(i=1;i<n;i++) for(j=1;j<=n-i;j++) x++;（6）x=n; /n>1 y=0; while(x≥(y+1)(y+1)) y++;

试分析下面各算法的时间复杂度。

（1）x=90;y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

else x++;

（2）for(i=0;i<n;i++)

for(j=0; j<m; j++)

a[i][i]=0;

（3）s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=B[i][i];

sum=s;

（4）i=1;

while(i<=n)

i=i*3;

（5）x=0;

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

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

x++;

（6）x=n; //n>1

y=0;

while(x≥(y+1)*(y+1))

y++;

题目解答

针对这道题进行逐项分析：

（1）这段代码是一个循环语句，其中根据条件判断进行了不同的操作。根据给定的初始值，循环执行的次数取决于变量y的值。x的值在循环内递增或递减，直到y的值小于等于0为止。时间复杂度为O(y)。

（2）这段代码是两个嵌套的循环语句，其中对二维数组a进行了赋值操作。循环的次数取决于变量n和m的值，即n*m。时间复杂度为O(n*m)。

（3）这段代码是两个嵌套的循环语句，其中对二维数组B进行了累加操作。循环的次数取决于变量n的值，即n*n。时间复杂度为 $O(n^2)$ 。

（4）这段代码是一个循环语句，其中变量i的值每次乘以3。循环的次数取决于变量n的值，即log3(n)。时间复杂度为O(log3(n))。

（5）这段代码是两个嵌套的循环语句，其中对变量x进行了自增操作。循环的次数取决于变量n的值，即n*n。时间复杂度为 $O(n^2)$ 。

（6）这段代码是一个循环语句，其中变量y的值递增，直到满足条件。循环的次数取决于变量x的值，即sqrt(n)。时间复杂度为O(sqrt(n))。

综上所述，故答案为：

（1）时间复杂度为O(y)；

（2）时间复杂度为O(n*m)；

（3）时间复杂度为 $O\left(n^2\right)$ ；

（4）时间复杂度为O(log3(n))；

（5）时间复杂度为 $O\left(n^2\right)$ ；

（6）时间复杂度为O(sqrt(n))