算法复习题

1．什么是算法？算法必须满足的五个特性是什么？

算法：一组有穷的规则，规定了解决某一特定类型问题的一系列运算。（有限指令的集合，遵循它可以完成一个特定的任务）.

必须满足的五个特性是(遵循以下五条准则)： 1．有穷（限）性 2．确定性 3．可（能）行性 4．输入（n≥0） 5．输出（n≥1）

2．对算法进行分析分哪两个阶段？各自完成什么任务（分别得到什么结果）？ 对一个算法要作出全面的分析可分成两个阶段进行，即：事前分析和事后测试。

事前分析求出该算法的一个时间界限函数；

事后测试搜集此算法的执行时间和实际占用空间的统计资料。

3．证明：若f1(n)=O(g1(n))并且f2(n)= O(g2(n))，那么f1(n) +f2(n)= O(max{g1(n), g2(n)}

证明：

根据f1(n)=O(g1(n))可知，存在正常数C1，当n≥n0时，使得|f1(n)|≤C1|g1(n)|；

同理，根据f2(n)= O(g2(n))可知，存在正常数C2，当n≥n0时，使得|f2(n)|≤C2|g2(n)|

当n≥n0时，|f1(n)+f2(n)|≤|f1(n)|+|f2(n)|≤C1|g1(n)|+C2|g2(n)| ≤C1|gk(n)|+C2|gk(n)|

≤（C1+C2）|gk(n)|， 其中gk(n)=max{g1(n),g2(n)}，

k={1,2}

当n≥n0时，取C=（C1+C2），据定义命题得证。

4．如果f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n))，下列说法是否正确？试说明之。

（a） f1(n) +f2(n)= Θ(g1(n)+ g2(n)) （b） f1(n) +f2(n)= Θ(min{g1(n), g2(n)}) （c） f1(n) +f2(n)= Θ(max{g1(n), g2(n)}) 答：（a）和（c）均正确，（b）错误。

（a）正确可以根据定义直接证得。

（b）错误可举反例。例：f1(n)= 2n，f2(n)=2 n2 下面证明（c）正确性.

根据上题已经证明f1(n)+f2(n)= O(max{g1(n),g2(n)})，下面只需证明f1(n)+f2(n)= Ω(max{g1(n), g2(n)})，即存在正常数C，使得|f1(n)+f2(n)|≥C(max{g1(n), g2(n)})

根据f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n)) 得到，当n≥n0时，存在正常数C1、C2 、C3、C4

C1|g1(n)|≤|f1(n)|≤C3|g1(n)|

C2|g2(n)|≤|f2(n)|≤C4|g2(n)|

不妨设max{g1(n), g2(n)}= g1(n)

由于|f1(n)+f2(n)|≥||f1(n)|-|f2(n)||≥|C1|g1(n)|-C3|g2(n)||

=C|max{g1(n), g2(n)}|

取C≥|C1-C3|的正常数，由定义得 f1(n)+f2(n) = Ω(max{g1(n), g2(n)})

命题得证。

5．证明 |「log2n」|= O(n) 证明：对于任意的正整数n，

|「log2n」|≤|log2（n+1）|≤|n+1|≤2|n| 取n0=1，C=2，根据定义知命题成立。

6．证明 3n「log2n」= O(n2)

证明：对于任意的正整数n，|3n「log2n」|≤|3n「log2n」|≤3|n2| 取n0=1，C=3，根据定义知命题成立。

7．用数学归纳法证明：当n≥1时，?i?n(n?1)/2.

i?1n证明：当n=1时，?i?1，n(n+1)/2=1，命题成立；

i?1n 假设n=k-1时，?i?n(n?1)/2成立;（k≥2）

i?1n 当n=k时，?i?n(n?1)/2=?i?k(k?1)/2?k=k(k+1)/2

i?1i?1nn综上可知，命题成立。 8．在下列情况下求解递归关系式

?g(n)n足够小 T(n)= ?

2T(n/2)?f(n)否则?当①n=2k g(n)= O(1)和f(n)= O(n)； ②n=2k g(n)= O(1)和f(n)= O(1)。

解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k)

=??

=2kT(1)+2k-1f(2)+2k-2f(22)+?+20f(2k) =2kg(n)+ 2k-1f(2)+2k-2f(22)+?+20f(2k) ①当g(n)= O(1)和f(n)= O(n)时，

不妨设g(n)=a，f(n)=bn，a，b为正常数。则

T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+?+20*2kb =2ka+kb2k

=an+bnlog2n= O(nlog2n) ②当g(n)= O(1)和f(n)= O(1)时，

不妨设g(n)=c，f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+?+20d=c2k+d(2k-1)

=(c+d)n-d= O(n)

h(1)?19．求解递推关系式：

h(n)?2h(n?1)?1

解：构造生成函数

H(x)?h(1)x?h(2)x????h(k)xk

2k?1?求解H(x)

H(x)?h(1)x?h(2)x2???2xH(x)??2h(1)x?2h(2)x??23

(1?2x)H(x)?x?x2?x3???H(x)?x

(1?2x)(1?x)x (x?1) 1?x分解H(x)成幂级数 令H(x)?AB 则A=-1 B=1 ?1?x1?2x

?11?H(x)????(1?x?x2??)?(1?2x?(2x)2?(2x)3??)

1?x1?2x?(2?1)x?(22?1)x2???(2n?1)xn??

??(2k?1)xkk?1?

所以?h(n)?2n?1

?T1?110．求解递推关系式：?

T?2T?2n?1?n解：

Tn?2Tn?1?2?2(Tn?2?2)?2?22Tn?2?22?2?2n?1T1?(2n?1???2)?3*2n?1?2

?F1?1?11．求解递推关系式：?F2?1

?F?F?F(n?2)n?1n?2?n解：以Fn为系数，构成生成函数F(x)

F(x)?F1x?F2x2?? xF(x)?F1x2?F2x3??

?x2F(x)?F1x3?F2x4??(1?x?x2)F(x)?F1x?(F2?F1)x2?(F3?F2?F1)x3???xF(x)?x?21?x?x?xAB ??1?51?51?51?5(x?)(x?)x?x?2222A?1111(?1?) B?(?1?) 225515((???)x?(?2??2)x2?? 1?51?5 ?? 22F(x)?其中??

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法复习题在线全文阅读。