计算机算法基础 第2版 习题及答案 第1章 .docx

PAGE2

第1章 概述

假设f(n)和g(n)为两个定义域为自然数的正函数。证明f(n)+g(n)=?(max(f(n),g(n)))。

证明：因为对任一n≥0，max(f(n),g(n))≤f(n)+g(n)≤2max(f(n),g(n))，所以有f(n)+g(n)=

O(max(f(n),g(n)))和f(n)+g(n)=?(max(f(n),g(n)))，也就是f(n)+g(n)=?(max(f(n),g(n)))。

假设f(n)=?(p(n))，g(n)=?(q(n))，并且都是正函数。证明以下结论。

f(n)+g(n)=?(p(n)+q(n))

f(n)?g(n)=?(p(n)?q(n))

f(n)/g(n)=?(p(n)/q(n))

证明：因为f(n)=?(p(n))，g(n)=?(q(n))，所以存在常数a?0,b?0,c?0,d?0和n0使得

当n≥n0时有ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)。

从以上关系可知，当n≥n0时，ap(n)+cq(n)≤f(n)+g(n)≤bp(n)+dq(n)。

让u=min(a,c),v=max(b,d)，上式可写为

u(p(n)+q(n))≤f(n)+g(n)≤v(p(n)+q(n))

所以有f(n)+g(n)=?(p(n)+q(n))。

由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)，我们可得，当n≥n0时，

ap(n)?cq(n)≤f(n)?g(n)≤bp(n)?dq(n)。

让u=a?c,v=b?d，上式可写为

u(p(n)?q(n))≤f(n)?g(n)≤v(p(n)?q(n))。

所以有f(n)?g(n)=?(p(n)?q(n))

由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n),我们可得，当n≥n0时，

ap(n)/dq(n)≤f(n)/g(n)≤bp(n)/cq(n)。

让u=a/d,v=b/c，上式可写为

u(p(n)/q(n))≤f(n)/g(n)≤v(f(n)/q(n))。

所以有f(n)/g(n)=?(p(n)/q(n))。

对以下每个函数，用theta(?)记号表示与其同阶的只含一项的函数。例如，f(n)=(n+1)3可表示为f(n)=?(n3)。

(a)f(n)=n2+nlgn

(b)f(n)=n

(c)f(n)=(

解：

(a)f(n)=n2+nlgn=Q(n2)

(b)f(n)=n(nlgn+2n)lg2n+n=

(c)f(n)=(n2+lgn)(n+1)n+n

用theta(?)记号表示对下面一段程序中语句x?x+1被执行的次数的估计。

fori?1ton

forj?ito3i

x?x+1;

endfor

endfor

解：T(n)=i=1

=i=1

=2n(n+1)2+

=Q(n2)。

对以下每个级数和T(n)，用theta(?)记号表示与其同阶的只含一项的函数。

T(n)=k=1

T(n)=k=1

解：(a)因为T(n)=k=1nk3lgk+1k2

T(n)ck=1nklgkc=cn2lgn。所以有T(n)=O(n2

又因为T(n)=k=1nΘ(klgk)，所

T(n)dk=1nklgkdk=n/2nklgkdk=n/2nn/2lgn/2=d?n

所以有T(n)=?(n2lgn)和T(n)=?(n2lgn)。

(b)T(n)=k=1nk+klgk+83k2lgk+5k+1=

在我们讨论例1.3的线性有哪些信誉好的足球投注网站算法的平均复杂度时，我们假设数字x总可以在数组A中找到。这简化了问题。如果我们假定，x不出现在数组A中的概率是Pr(x?A[1..n])=0.2，而x等于A中任一个数的概率相同，即Pr(x=A[1])=Pr(x=A[2])=…=Pr(x=A[n])，求线性有哪些信誉好的足球投注网站算法的平均复杂度。

解：平均复杂度是：0.2?n+1-0.2n(1+2+…+n)=0.2n+0.8n+12=0.6n