《计算机常用算法与程序设计教程(第2版)》

部分习题解答提示

习题1

1-1求出以下程序段所代表算法的时间复杂度

(1)解：因s=1+2+…+n=n(n+1)/2

时间复杂度为0(n2)。

(2)解：设n=2u+1,语句m=m+1的执行频数为

s=1+1+2+2+3+3+…+u+u=u(u+1)=(n-1)(n+1)/4

设n=2u,语句m=m+1的执行频数为

s=1+1+2+2+3+3+…+u=u2=n2/4

时间复杂度为0(n2)。