第一章 作业
1. 证明下列Ο、Ω和Θ的性质 1）
f=Ο(g)当且仅当g=Ω(f)
证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n?n0，有f? c1*g(n)。由于c1?0，故g(n) ? 1/ c1 *f(n)，故g=Ω(f)。
必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n?n0，有g(n) ? c2 *f(n).由于c2?0，故f(n) ? 1/ c2*f(n)，故f=Ο(g)。 2）
若f=Θ(g)则g=Θ(f)
证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n?n0，有c1*g(n) ?f(n) ? c2*g(n)。由于c1?0，c2?0，f(n) ?c1*g(n)可得g(n) ? 1/c1*f(n)，同时，f(n) ?c2*g(n)，有g(n) ? 1/c2*f(n)，即1/c2*f(n) ?g(n) ? 1/c1*f(n)，故g=Θ(f)。 3）
Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。
证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n?n1，有
F(n) ? c1 (f(n)+g(n)) = c1 f(n) + c1g(n)
? c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g}
所以，F(n)= Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。
4）
log(n!)= Θ(nlogn)
1
证明：
?由于log(n!)=?logi ??logn=nlogn，所以可得log(n!)= Ο(nlogn)。
i?1i?1nn?由于对所有的偶数n有，
log(n!)= ?logi??logi??logn/2?(n/2)log(n/2)=(nlogn)/2-n/2。
i?1i?n/2i?n/2nnn当n?4，(nlogn)/2-n/2?(nlogn)/4，故可得?n?4，log(n!) ?(nlogn)/4，即log(n!)= Ω(nlogn)。
综合以上两点可得log(n!)= Θ(nlogn)
2. 设计一个算法，求给定n个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法：
Void findsecond(ElemType A[]) {
for (i=2; i<=n;i++) if (A[1]
temp=A[1];
A[1]=A[i]; A[i]=temp;
}
for (i=3; i<=n;i++) if (A[2]
2
{
temp=A[1];
A[1]=A[i]; A[i]=temp;
} return A[2]; }
该算法使用的比较次数为：2n-3
3. 设计一个算法，求给定n个元素的最大和最小元素。（要求算法的复杂度至多为1.5n） 算法：
void Maxmin2(A;l,r;int x;int y); {
if (l=r) { x=A[l]; y=A[r]; return;} if (r-l=1)
{ if (A[l]
else { mid:=(l+r) div 2;
Maxmin2(A,l,mid,x1,y1); Maxmin2(A,mid+1,r,x2,y2);
3
x=min(x1,x2); y=max(y1,y2); } }
该算法使用的比较次数为：1.5n-2
4. 给定多项式p(x)=anxn+ an-1xn-1+…+a1x+a0，假设使用以下方法求解： p=a0; xpower=1; for (i=1; i<=n; i++) { xpower=x * xpower; p=p+ai * xpower; }
求（1）该算法最坏情况下使用的加法和乘法分别为多少次？ （2）能不能对算法的性能进行提高？
解：（1）该算法最坏情况下使用的加法n次，乘法2n次 （2）改进的算法为：
float Horner(A, float x) {
p=A[n+1]; for (j=1; j<=n; j++) p=x*p+A[n-j]; return p;
}
该算法中使用加法n次，乘法n次
4
第二章
1．求解下列递推关系：
1）当n≥1时，f(n)=3f(n-1)；f(0)=5
解：f(n)=3f(n-1)=32f(n-2)=…=3nf(n-n)= 3n *5=5*3n
2) 当n≥2时，f(n)=5f(n-1)-6f(n-2)； f(0)=1；f(1)=0 解：该递推关系的特征方程为：x2-5x+6=0 特征根为：r1=2；r2=3 故f(n)=c1*2n+c2*3n
有f(0)= c1*20+c2*30== c1+c2=1 且f(1)= c1*21+c2*31== 2c1+c32=0 可得c1 =3， c2=-2 故f(n)=3*2n-2*3n
3) 当n≥1时，f(n)=f(n-1)+n2； f(0)=0 解：f(n)= f(n-1)+n2 = f(n-2)+ (n-1)2+n2 =….
= f(0)+12+22+…+ (n-1)2+n2 =12+22+…+ (n-1)2+n2 =1/6 n(n+1)(2n+1)
4) 当n≥1时，f(n)=2f(n-1)+n2； f(0)=1 解：设f(n)=2nf’(n)，且f’(0)= f(0)=1
5