《计算机算法基础》第三版_课后习题答案

3.0 文小白 2023-09-15 141 0 452.5KB 11 页 10文币

侵权投诉

4.2 在下列情况下求解递归关系式

T(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)

4.3 根据教材中所给出的二分检索策略，写一个二分检索的递归过程。

Procedure BINSRCH(A, low, high, x, j)

integer mid

if low≤high then

mid←

if x=A(mid) then j←mid; endif

if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif

if x<A(mid) then BINSRCH(A, low, mid-1, x, j); endif

else j←0; endif

end BINSRCH

4.5 作一个“三分”检索算法。它首先检查 n/3 处的元素是否等于某个 x 的值，

然后检查 2n/3 处的元素；这样，或者找到 x，或者把集合缩小到原来的 1/3。分

析此算法在各种情况下的计算复杂度。

Procedure ThriSearch(A, x, n, j)

integer low, high, p1, p2

low←1; high←n

while low≤high do

p1← ; p2←

case

:x=A(p1): j←p1; return

:x=A(p2): j←p2; return

:x<A(p1): high←p1-1

:x>A(p2): low←p2+1

:else: low←p1+1; high←p2-1

end case

repeat

j←0

end ThriSearch

T(n)=

g(n)= O(1) f(n)= O(1)

成功:

O(1), O(log3(n)), O(log3(n))

最好，平均，最坏

失败:

O(log3(n)), O(log3(n)), O(log3(n))

最好，平均，最坏

4.6 对于含有 n 个内部结点的二元树，证明 E=I+2n，其中，E，I 分别为外部和

内部路径长度。

证明：数学归纳法

① 当 n=1 时，易知 E=2，I=0，所以 E=I+2n 成立；

② 假设 n≤k(k>0)时，E=I+2n 成立；

③ 则当 n=k+1 时，不妨假定找到某个内结点 x 为叶结点（根据二元扩展

树的定义，一定存在这样的结点 x，且设该结点的层数为 h），将结点 x 及其左

右子结点（外结点）从原树中摘除，生成新二元扩展树。此时新二元扩展树内部

结点为 k 个，则满足 Ek=Ik+2k，考察原树的外部路径长度为 Ek+1= Ek-（h-

1）+2h，内部路径长度为 Ik+1=Ik+（h-1），所以 Ek+1= Ik+2k+h+1= Ik+1+2k+2=

Ik+1+2(k+1)，

综合①②③知命题成立。

4.10 过程 MERGESORT 的最坏情况时间是 O(nlogn)，它的最好情况时间是什么？

能说归并分类的时间是 Θ(nlogn)吗？

最好情况：是对有序文件进行排序。

分析：在此情况下归并的次数不会发生变化----log(n)次

归并中比较的次数会发生变化（两个长 n/2 序列归并）

最坏情况

两个序列交错大小，需要比较 n-1 次

最好情况

一个序列完全大于/小于另一个序列，比较 n/2 次

差异都是线性的，不改变复杂性的阶

因此最好情况也是 nlogn, 平均复杂度 nlogn。

可以说归并分类的时间是 Θ(nlogn)

4.11 写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。

答：见《数据结构》

算法 MPass（R，n，1ength．X）

MP1 [初始化]

i¬1 ．

MP2 [合并相邻的两个长度为 length 的子文件]

WHILE i ≤ n – 2*length + 1 DO

（Merge（R，i，i＋length–l，i＋2*length–1．X）.

i¬i＋2*length ）．

MP3 [处理余留的长度小于 2*length 的子文件]

IF i+length–1 < n

THEN Merge（R，i，i+length–1，n. X）

ELSE FOR j = i TO n DO Xj←Rj ▌

算法 MSort(R，n) // 直接两路合并排序算法，X是辅助文件，其记录结构

与R相同

MS1 [初始化]

length¬1 ．

MS2 [交替合并]

WHILE length < n DO

（MPass（R，n，length．X）.

length¬2*length

if length > n

then FOR j = 1 TO n DO Rj←Xj

else MPass（X，n，length．R）.

length¬2*length）

endif

)

4.23 通过手算证明（4.9）和(4.10)式确实能得到 C11,C12,C21 和 C22 的正确值。

P=(A11+A22)(B11+B22) T=(A11+A12)B22

Q=(A21+A22)B11 U=(A21-A11)(B11+B12)

R=A11(B12-B22) V=(A12-A22)(B21+B22)

S=A22(B21-B11)

C11=P+S-T+V

=(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22)

=A11B11+A22B11+A11B22+A22B22+A22B21

-A22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22

=A11B11 +A12B21

C12=R+T

= A11B12-A11B22 +A11B22+A12B22

= A11B12 +A12B22

C21=Q+S

= A21B11+A22B11 +A22B21-A22B11

= A21B11 +A22B21

C22=P+R-Q+U

=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12)

=A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 文币 0人已下载

立即下载

摘要：

4.2在下列情况下求解递归关系式T(n)=当①n=2kg(n)=O(1)和f(n)=O(n)；②n=2kg(n)=O(1)和f(n)=O(1)。解:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2T(2k-2)+f(2k-1))+f(2k)=22T(2k-2)+21f(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+2...

展开>> 收起<<

《计算机算法基础》第三版_课后习题答案.doc

共11页,预览10页

还剩页未读，继续阅读

《计算机算法基础》第三版_课后习题答案

相关推荐

开通VIP享超值会员特权

作者详情

相关文档

推荐作者

热门标签

举报选择: