1.3.2 答案解析
一、单项选择题
1、D。
2、B。
3、A。
4、D。
5、A。分析：该算法中的基本操作是while循环中的x=2*x，设while循环次数为f（n），则变量i从3到f（n），因此循环次数为3*2f（n）＜n/2，则
，故时间复杂度为O（log2 n）。
6、C。分析：与上题类似，该算法的时间复杂度主要耗费在语句i=i*3，设while循环次数为f（n），则有3f（n）≤n，则3 f（n）≤log n，故时间复杂度为O（log3 n）。
7、B。分析：该算法中的基本语句为while循环中的i++和s+=i两条语句，循环体是在完成等差数列求和，设循环次数为k，则s=0+1+2+3+…+k=（1+k）k/2<n，即
，故时间复杂度为
。
8、B。分析：这是一个求n的阶乘递归算法实现。每次递归调用fact函数，将参数n减1，当n==1时，递归调用结束，共执行n次递归调用fact函数，因此时间复杂度为O（n）。
9、B。分析：基本语句为while循环中的y=y+1，假设循环执行k次，则执行第k次循环时有（y+1）2<=n，y的初始值为1，执行到第k次时，有（k+2）2<=n，则
，故时间复杂度为
。
10、C。分析：与上题类似，基本语句为while循环中的i++，假设循环执行k次，执行到第k次时，有k3<=n，则
，因此时间复杂度为
。
二、综合分析题
1、正确性、可读性、健壮性、高效率和低存储量。
2、集合、线性、树、图。
3、关系。
4、（3+n）*（n-2）/2。分析：n+n-1+…+3=（3+n）*（n-2）/2。
5、O（n*m）。
三、算法分析题
1、分析：该题与例1-4的思路非常类似，设n=2k（k≥0），由定义可得：
T（2k）=2T（2k-1）+2k=22T（2k-2）+2*2k
以此类推，T（2k）=2iT（2k-i）+i*2k
因此，当i=k时，T（2k）=2kT（20）+k*2k=2kT（1）+k*2k=2k+k*2k=2k（1+k）
即T（n）=n（1+k）=n（1+log2n）=O（nlog2n）
2、（1）函数fun（n）的返回值为count的值，这是一个三重循环，count的执行次数直接与i、j、k的取值有关，当i的值确定时，j的取值范围也随之确定，k的取值范围也可确定下来。只有当i和j的值确定了之后，k的取值范围才能确定，k的取值直接决定着count的执行次数。由此，我们可以分别令i=1、2、3、...、n时，j=n、n-1、n-2、...时，再确定k的取值范围，最后求count的执行次数。第一层循环判断次数为n+1次，其内层语句执行n次；第二层循环执行次数为n+（n-1）+（n-2）+...+2+1；第三层循环执行次数与i和j的值有关，其执行次数可通过表1-1进行分析。
表1-1 第三层for循环语句的执行次数
根据以上分析，count的执行次数为（1+2+3+...+n）+（2+3+4+...+n）+...+（n-1+n）+n=n（n+1）（2n+1）/6。其证明过程需要利用等差和等比数列性质，count的执行次数记作S，则S=1+2*2+3*3+…+n*n=12+22+32+…+n2。
证明：这里利用恒等式（n+1）3=n3+3n2+3n+1来证明此结论。
根据以上恒等式，可知：
(n+1)3-n3=3n2+3n+1
n3-(n-1)3=3(n-1)2+3(n-1)+1
...
33-23=3*22+3*2+1
23-13=3*12+3*1+1
将以上n个等式两端分别相加，可得：
(n+1)3-1=3(12+22+32+…+n2)+3(1+2+3+…+n)+n
又有1+2+3+...+n=n（n+1）/2，因此有：
n3+3n2+3n=3(12+22+32+…+n2)+3n(n+1)/2+n=3S+3n(n+1)/2+n
将以上式子整理：
S=n(n+1)(2n+1)/6
（2）n=6时，fun（6）=91。
当两重循环结束后，就会输出一次count的值，第i次输出count的值就是表1-1中前i列值之和。函数fun（6）的输出结果为：
count=21
count=41
count=59
count=74
count=85
count=91
3、分析：归并排序算法和快速排序算法的结构完全一致，因此，其时间复杂度的分析方法与快速排序一样。所以，在MergeSort（）函数中，调用了Merge（）函数，而Merge（）的时间复杂度为O（n），在MergeSort（）函数中，又调用了两次自身。下面来分析该算法的时间复杂度。
由于Merge（）函数的时间复杂度为O（n），假设Merge（）函数的基本操作次数为c*n，其中，c为常数，MergeSort（）函数的基本操作次数为f（n），从而得出：
令n=2k，则有f（n）=nf（1）+cnlog2 n，而根据MergeSort函数的实现算法，有f（1）=O（1），则可得f（n）=nO（1）+cnlog2 n，因此MergeSort函数的时间复杂度为T（n）=O（nlog2 n）。