《数据结构习题》《严蔚敏》部分答案.pdfVIP

《数据结构》习题集1－5 章部分课后习题解答： （注：有的题目可能并非作业题，也可能和作业题目类似，供大家参考） 第一章习题 P9 1.8 （5 ）for(i=1; i=n; i++) for(j=1; j=i; j++) for(k=1; k=j; k++) @ x += delta; 第一层循环 第二层循环 第三层循环 @语句 for(i=1; i=n; i++) for(j=1; j=i; j++) for(k=1; k=j; k++) i=1 j=1 1 1 j=1 1 1 i=2 j=2 2 2 n j=1 1 1 i=3 j=2 2 2 j=3 3 3 ... ... ... ... i=n （1+2+3+…+n ） @语句执行频度 =1+(1+2)+(1+2+3)+…+(1+2+3+…+n) =n*1+(n-1)*2+(n-2)*3+…+1*n n = ∑x (n −x +1) x 1 1.9 分析：算法的时间复杂度，课本上是这样定义的：算法中基本操作重复执行的次数是问 题规模n 的某个函数f(n)，算法的时间量度记做T(n)=O(f(n)) ，他表示随问题规模n 的增大， 算法执行时间的增长率和f(n)的增长率相同，称做算法的时间复杂度。 T(n)=O(f(n)) 的数学解释：如果存在正的常数 c 和自然数 , 使得当 时有 n n ≥n 0 0 T (n) ≤cf (n) 则称函数T(n)当n 充分大时有上界（up bound ），且f(n)是它的一个上界，记 做T(n)=O(f(n))，称T(n) 的阶不高于f(n)的阶。 如何求时间复杂度：1）首先找到基本操作，一般指包含在最深层循环中的原操作。2 ） 计算执行频度。3 ）表示成T(n)=O(f(n)) 的形式 答：1）寻找基本操作：x*2=2; count++; 2 ）执行频度：x 初值为2 ，终止值为n/2 ，每次增量为*2 ⇒ 执行频度= log2 n / 2 3 ） 存 在 常 数 c1 ， c2 和 自 然 数 n0 使 得 得 当 n ≥n0 时 有 log n / 2 ≤c log n / 2 ≤c log n ，所以根据定义时间复杂度为 T(n)=