算法分析习题.ppt

算法分析习题课 计算机算法分析—习题课 第四章：2 、3、 5、6、10 第五章：2、3 、8 、 9 、11 、 12 4-2 4-2 当g(n)=O(1)和f(n)=O(n)时 不妨设g(n)=a，f(n)=bn，则： T(n)=2T(n/2)+bn =4T(n/4)+2bn = … = 2kT(n/2k)+kbn =an+bnlog2n=O(nlog2n) 4-2 当g(n)=O(1)和f(n)=O(1)时， 不妨设g(n)=c，f(n)=d，则： T(n)=2T(n/2)+d = 4T(n/4)+2d =2kT(n/2k)+kd =… =cn+d log2n =O(n) 4-3 根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) integer mid if low≤high then mid← ?(low+high)/2 ? case : x=A(mid): j←mid;return : xA(mid): BINSRCH(A, mid+1, high, x, j) : xA(mid): BINSRCH(A, low, mid-1, x, j) endcase else j←0; endif end BINSRCH 4-5 作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析算法在各种情况下的计算复杂度。 Procedure ThriSearch(A, n, x, j) integer low, high, p1, p2 low←1; high←n while low≤high do p1←?(high+2low)/3? p2←?(2high+low)/3? case :x=A(p1): j←p1;return :x=A(p2): j←p2;return :xA(p1): high←p1-1 :xA(p2): low←p2+1 :else: low←p1+1; high←p2-1 endcase repeat j←0 end ThriSearch 时间复杂度 成功: 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(k0)时，E=I+2n成立； 则当n=k+1时，不妨认定某个内结点x，而且它为叶结点（一定存在这样的x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除（x替换为外结点）。 4-10 过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？ 基于分治策略的算法-归并分类 Procedure MERGESORT(low,high) if lowhigh then mid←?(low+high)/2? call MERGESORT(low,mid) call MERGESORT(mid+1,high) call MERGE(low,mid,high) endif End MERGESORT 最好情况： 对有序文件进行排序 分析 递归的次数不会发生变化----log(n)次 归并中比较的次数会发生变化（两个长n/2序列归并） 最坏情况 两个序列交错大小 需要比较n-1次 最好情况 一个序列完全大于/小于另一个序列 比较n/2次 差异都是线性的，不改变复杂性的阶 最好情况时间是O(nlogn) ，平均复杂度O(nlogn)。 第五章：2、3 、8 、 9 、11 、 12 5-2 ①求以下情况背包问题的最优解，n=7，m=15，(p1 ,…, p7)=(10,5,15,7,6,18,3)和(w1,…,w7) = (2,3,5,7,1,4