计算机图形学算法答案(6)

习题5.5 2. Hints: a. 减常因子 b.

c.

d.折半查找在最坏情况下的查找效率是log2n+1.而

26

习题6.1 1. hint sort the list and then simply return the n/2th elements of the sorted list. 效率: 假设排序算法的效率是O(nlogn),那么该算法的效率是O(nlogn)+Θ(1)= O(nlogn) 3.hint a. 初始化C=A∩B=Φ for every element ai in A do (1<=i<=n) for every element bj in B (1<=j<=m) If ai=bj add ai to C delete bj from B 最差情况:C为空,比较的次数是nm. b.方法一: 排序集合A For every element bj in B 用二分查找的办法在A中查找与bj相匹配的元素a If 查找成功 Add a to C 效率分析: 假设排序的效率是O(nlogn),则该算法效率 O(nlogn)+mO(logn)=(n+m)O(logn) 方法二: 首先对A和B都分别排序. 然后对A和B应用合并排序,只输出它们的公有元素. 效率分析: 假设排序的效率是O(nlogn),则该算法效率 O(nlogn)+O(mlogm)+Θ(n+m)=O(slogs) where s=max{n,m} 方法三: 首先将A和B合并为L 排序L 从左至右成对扫描L If Li=Li+1 Add Li to C i←i+2 效率分析: 假设排序的效率是O(nlogn),则该算法效率 O((n+m)logn))+ Θ(n+m) =O(slogs) where s=max{n,m} 4.hint a. 排序数组,然后返回它的第一和最后元素. 假设排序的效率是O(nlogn),则该算法效率O(nlogn)+Θ(1)+Θ(1)= O(nlogn) b.蛮力和分治都是线性的,所以优于基于预排序的算法 习题6.3 2.b. 27

4.a.

28

5.a.

二叉查找树中最大值和最小值分别是树中最右边和最左边的结点.因此,从根开始,沿着向左的路径一直走到这样的结点:它的左孩子为空.这个结点里的值就是最小值.同理,可以找到最大值.最后,这两个值做一次减法运算即可.

算法的效率: Θ(logn)+ Θ(logn)+ Θ(1)= Θ(logn) b.错误.

8.

不成立.

例如:列表{A,B},查找A,二分查找只做1次比较.而在2-3树中查找则要做2次比较 习题6.4 1.

29

a. b. c. 错误.对于列表{1,2,3} 按自顶向下:{3,1,2} 自底向上:{3,2,1} 5.a.设计一个算法,寻找并删除堆中最小元素,然后确定其时间效率 Hints: 最小元素一定在堆的叶子中. 在堆H[1..n]的后半部分,(H[ n/2 +1],?,H[n])中查找最小元素,并与最后的元素H[n]互换,删除最后的元素.堆规模降1,如果必要的话,调整元素H[n],使其满足双亲优势. 效率分析: 查找:Θ(n) 交换并删除: Θ(1)+ Θ(1) 调整为堆:O(logn) b.设计一个算法,在给定的堆H中寻找并删除一个包含给定值v的元素,然后确定其时间效率. Hints: 在H中顺序查找满足条件的第一个元素H[i]. H[i]与H[n]互换. 删除最后元素 堆规模降1 调整元素H[n]使其满足双亲优势 效率分析: 查找:Θ(n) 交换并删除: Θ(1)+ Θ(1) 调整为堆:O(logn) 习题6.5 1. 30