《算法导论第一次习题》由会员分享，可在线阅读，更多相关《算法导论第一次习题（21页珍藏版）》请在装配图网上搜索。
1、算法导论第一次习题课2.1-2 INSERTION-SORT非升序排序有同学改成从lengthA到2循环，此时A j+1lengthA是循环不变式INSERTION-SORT(A)for j2 to lengthA do keyAj /Insert Aj into the sorted sequence A1.j-1 ij-1 while i0 and Ai19 flag110 if flag=111 Cn+1 1A、B各存放了一个二进制n位整数的各位数值，现在通过二进制的加法对这两个数进行计算，结果以二进制形式把各位上的数值存放在数组C中 key存储临时计算结果，flag为进位标志符，按位相
2、加，8、9行不能少2.2-1 (n3)2.2-2 Selection排序1 Select-sort(A,n)2 for i1 to n-13 minAi4 indexi5 for ji+1 to n6 if Ajr then return NILmid=(l+r)/2 /l+(r-l)/2If v=Amid then return midIf vAmid then return binary-search(A,v,mid+1,r)else return binary-search(A,v,l,mid-1)当mid+1错写成mid的时候，会使递归一直无法结束例：取A=3,4,v=9,则l=1,r
3、=2,mid=1binary-search(A,v,1,2)mid=(l+r)/2=1因vAmid,执行binary-search(A,v,1,2)判断出集合S中是否存在有两个其和等于x的元素算法思想：首先要对n个数进行排序，用快排复杂度为 ，然后再在排序后的数组中查找是否存在两数之和为x。假设排序后数组中元素为非降序列：13579101315ijx=15证明，可取c1=1/2,c2=1证明充分性的时候，不要忘了取n0=max(n1,n2)基本数学变换，略函数是否有界问题3.2-7 证明：用归纳法证明4.1-2 证明T(n)=2T(n/2)+n的解为证明：用代换法 证明合并排序算法的“准确”递
4、归式(4.2)的解为 (4.2)：通过改变变量求解递归式：利用递归树来猜测递归式T(n)=3T(n/2)+n的一个好的渐近上界，并利用代换法来证明你的猜测：利用递归树来证明递归式T(n)=T(n/3)+T(2n/3)+cn的解是 其中c是一个常数4.2-4：利用递归树来找出递归式T(n)=T(n-a)+T(a)+cn的渐近紧确解，其中a=1且c0是常数 4.3-1 用主方法确定渐近界：a)T(n)=4T(n/2)+n a=4,b=2,应用规则1)有 b)T(n)=4T(n/2)+n2 a=4,b=2,应用规则2)有c)T(n)=4T(n/2)+n3 a=4,b=2,应用规则3)有取c1/2就可
5、以使得4f(n/2)cf(n),所以T(n)=(n3)4.3-3 证明二分查找递归式T(n)=T(n/2)+(1)的解是T(n)=(lgn)考虑在某个常数c1时规则性条件af(n/b)=1,b1以及一个函数f(n),满足主定理第三种情况中的除了规则条件之外的所有条件的例子6.1-3 证明在一个最大堆的某个子树中，最大元素在该子树的根上证明：使用反证法，如果不是最大元素的话就违反了APARENT(i)=Ai，产生矛盾6.1-5 不一定是最小堆，降序时是最大堆6.1-6 不是最大堆，5,6,7这个子树不满足最大堆定义6.2.1 略6.2.6 最坏情况下，i=1而且Ai为堆中最小值，此时需要递归调用
6、 lgn 次，所以为(lgn)6.3.1 略6.3.3 注意各个节点高度的定义：与最远叶子节点的距离6.4.1 略6.4.3 对排序中，不管是元素是增序还是降序，建堆的时间均为O(n),n-1次调用MAX-HEAPIFY,需要时间O(nlgn).6.4.4 略6.5.1 提取大顶堆最大值，见HEAP_EXTRACT-MAX(A)算法6.5.2 向堆中插入新元素，注意先生成一个新的元素并赋值为-.6.5.3 略:略如果遇到中英版有出路,请标注你是使用哪一版本,方便我们批发作业:返回是r/不是r-1一种理解：只对全部相同这种情况进行处理，直接返回(p+r)/2。另一种理解：对部分相同也是取其中间位置，具体思路：使用一个计数器，记录当前划分元相同个数(4)，算法返回的值i+1(r-1)记为high（可以通过减去计数器+1(r-1-4+1)记为low，确定其相同范围）与(p+r)/2 比较，如果小于high且low(p+r)/2，返回为low,否则返回为high.134555515ipr(p+r)/27.2.2 当A中元素都相等时，PARTITION算法中第4行总满足，将n个数划分成1和n-1两部分，此时快排运行时间为(n2)7.2.3 降序运行时间同样为(n2)7.4.2 最优情况下：递归式 根据主定理求解(nlgn)7.4.3 略endTHANKS
算法导论第一次习题
