数据结构作业 01 - 详细解答
- 格式：doc
- 大小：32.50 KB
- 文档页数：2
分析下列各程序的时间复杂度（问题的规模为n, n>100）：
1.
j=1;
k=0;
do
{ k=k+10*j; j++;
}while(j!=n);
循环体每执行一次j增1，因此，重复执行n-1次。
∴ T(n) = O(n)
2.
m=91; n=300;
while(n>0)
if (m>0)
{ m=m-10; n--;
}
else m++;
问题规模n是常数（300），这段程序总是在常量时间内执行完成。
∴ T(n) = O(1)
3.
for(i=0; i
∴ T(n) = O(n2)
4.
i=1; k=1;
while(i<=n-1)
{ k=k*10*i;
i++;
}
循环体每执行一次i增1，因此，重复执行n-1次。
∴ T(n) = O(n)
5.
i=1; j=0;
while(i+j<=n)
if(i>j) j++; else i++;
每循环一次，i或j增1，且非同时增1，即i+j增1。循环重复执行n次。
∴ T(n) = O(n)
6.
for(i=0; i
1+22+32+42 … +(n-1)2 = n(n-1)(2n-1)/6
（上式证明参见初等代数）
∴ T(n) = O(n3)
7.
x=n;
y=0;
while(x>=(y+1)*(y+1)) y++;
每循环一次y增1，当y+1增至n1/2时，循环结束。即，循环重复执行n1/2次。
∴ T(n) = O(n1/2)
8.
i=-1; s=0;
while(s
}
∵ i是奇数，且每次循环增2，假设循环需重复执行m次，则有
s=1+3+5+ … +2m-1>=n
m>=n1/2
∴ T(n) = O(n1/2)
9.
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
for(k=1; k<=j; k++) x=sqrt(abs(x++));
x= sqrt(abs(x++))的重复执行次数为
1+22+32+42 … +n2 = n(n+1)(2n+1)/6
∴ T(n) = O(n3)
