程序段时间复杂度分析及计算

程序段时间复杂度分析及计算

本文将对以下程序段进行时间复杂度分析，并给出具体的计算结果：

(1)

x=90; y=100; 

while(y>0)
	if(x>100)
	 {x=x-10;y--;}
	else x++;

时间复杂度为 O(y)，其中 y=100，因此时间复杂度为 O(1)。

(2)

for (i=0; i<n; i++)
for (j=0; j<m; j++)
a[i][j]=0;

时间复杂度为 O(nm)，其中 n 和 m 分别为二维数组 a 的行数和列数。

(3)

s=0;
	for i=0; i<n; i++)
for(j=0; j<n; j++)
		s+=B[i][j];
sum=s;

时间复杂度为 O(n^2)，其中 n 为二维数组 B 的行数和列数。

(4)

i=1;
	while(i<=n)
		i=i*3;

时间复杂度为 O(log3n)。

(5)

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

时间复杂度为 O(n^2)。

(6)

x=n; //n>1
y=0;
while(x≥(y+1)* (y+1))
	y++;

时间复杂度为 O(sqrt(n))。

通过以上分析，我们可以清晰地了解每个程序段的时间复杂度，并根据其时间复杂度来评估算法的效率。