《数据结构作业 01 - 详细解答》由会员分享,可在线阅读,更多相关《数据结构作业 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=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)