《【2017年整理】数据结构作业01-详细解答》由会员分享，可在线阅读，更多相关《【2017年整理】数据结构作业01-详细解答（2页珍藏版）》请在金锄头文库上搜索。
分析下列各程序的时间复杂度（问题的规模为 n, n100）：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(n0)if (m0) m=m-10; n-;else m+;问题规模 n 是常数（ 300） ，这段程序总是在常量时间内执行完成。 T(n) = O(1)3.for(i=0; ij) j+; else i+;每循环一次，i 或 j 增 1，且非同时增 1，即 i+j 增 1。循环重复执行 n 次。 T(n) = O(n)6. for(i=0; i=(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=nm=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)
