算法导论第一次习题课.

Presentation on theme: "算法导论第一次习题课."— Presentation transcript:

1 算法导论第一次习题课

2 2.1-2 INSERTION-SORT非升序排序
INSERTION-SORT(A) for j←2 to length[A] do key←A[j] //Insert A[j] into the sorted sequence A[1..j-1] i←j-1 while i>0 and A[i]<key do A[i+1] ← A[i] i←i-1 A[i+1] ← key 有同学改成从length[A]到2循环，此时A[ j+1…length[A]]是循环不变式

3 2.1-4 两个二进制整数相加 A、B各存放了一个二进制n位整数的各位数值，现在通过二进制的加法对这两个数进行计算，结果以二进制形式把各位上的数值存放在数组C中 key存储临时计算结果，flag为进位标志符，按位相加，8、9行不能少 BINARY-ADD(A,B,C) 1 flag← 0 2 for j←1 to n 3 do key←A[j]+B[j]+flag //注意flag要清为0 flag← 0 7 C[j] ← key mod 2 8 if key >1 flag←1 10 if flag=1 11 C[n+1] ← 1 ө(n^3)

4 2.2-2 Selection排序 loop invariant: 从A[1]到A[j-1]，这j-1个数是排好序的，并且是A中最小的j-1个数。 最好和最差情况都是ө(n^2)，因为两层循环的复杂度是一样的 许多同学在第7行中直接exchange 另外，许多同学都没有对 loop invariant 进行说明 1 Select-sort(A,n) 2 for i←1 to n-1 3 min←A[i] 4 index←i 5 for j←i+1 to n 6 if A[j]< min index←j min←A[j] 9 if index != i A[index]←A[i] A[i]←min

5 2.3-2 改写MERGE过程，使之不使用哨兵元素。加一个判断把剩下哪一部分放入数组中 2.3-5二分查找算法
Binary-Search(A,v,l,r) if l>r then return NIL mid=(l+r)/2 // l+(r-l)/2 If v=A[mid] then return mid If v>A[mid] 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=2,mid=1 binary-search(A,v,1,2) mid =(l+r)/2=1 因v>A[mid],执行binary-search(A,v,1,2)

6 2.3-7判断出集合S中是否存在有两个其和等于x的元素
算法思想：首先要对n个数进行排序，用快排复杂度为 ，然后再在排序后的数组中查找是否存在两数之和为x。假设排序后数组中元素为非降序列： x=15 j i 1 3 5 7 9 10 13 15

7 3.1-1证明，可取c1=1/2, c2=1 3.1-5证明充分性的时候，不要忘了取n0=max(n1,n2) 3.2-2基本数学变换，略

8 3.2-4函数是否有界问题 3.2-7 证明： 用归纳法证明

9 4.1-2 证明T(n)=2T(n/2)+n的解为 证明：用代换法

10 4.1-4 证明合并排序算法的“准确”递归式(4.2)的解为

11 4.1-6：通过改变变量求解递归式 4.2-1：利用递归树来猜测递归式T(n)=3T(n/2)+n的一个好的渐近上界，并利用代换法来证明你的猜测 4.2-2：利用递归树来证明递归式T(n)=T(n/3)+T(2n/3)+cn的解是 其中c是一个常数 4.2-4 ：利用递归树来找出递归式T(n)=T(n-a)+T(a)+cn的渐近紧确解，其中a>=1且c>0是常数

12 4.3-1 用主方法确定渐近界： T(n)=4T(n/2)+n a=4,b=2,应用规则1)有
b) T(n)=4T(n/2)+n^ a=4,b=2,应用规则2)有 c) T(n)=4T(n/2)+n^ a=4,b=2,应用规则3)有 取c≥1/2就可以使得4f(n/2)≤cf(n),所以T(n)=ө(n^3)

13 4.3-3 证明二分查找递归式T(n)=T(n/2)+ө(1)的解是T(n)=ө(lgn)
4.3-5 考虑在某个常数c<1时规则性条件af(n/b)<=cf(n), 举一个常数a>=1,b>1以及一个函数f(n), 满足主定理第三种情况中的除了规则条件之外的所有条件的例子

14 6.1-3 证明在一个最大堆的某个子树中，最大元素在该子树的根上
证明：使用反证法，如果不是最大元素的话就违反了A[PARENT(i)]>=A[i]，产生矛盾 6.1-5 不一定是最小堆，降序时是最大堆 6.1-6 不是最大堆，{5,6,7}这个子树不满足最大堆定义

15 略 6.2.2

16 6.2.6 最坏情况下，i=1而且A[i]为堆中最小值，此时需要递归调用 lgn 次，所以为Ω(lgn)
6.3.1 略 6.3.3 注意各个节点高度的定义：与最远叶子节点的距离

17 6.4.1 略 6.4.3 对排序中，不管是元素是增序还是降序，建堆的时间均为O(n), n-1次调用MAX-HEAPIFY, 需要时间O(nlgn). 6.4.4 略

18 6.5.1 提取大顶堆最大值，见HEAP_EXTRACT-MAX(A)算法
6.5.2 向堆中插入新元素，注意先生成一个新的元素并赋值为-∞. 6.5.3 略

19 如果遇到中英版有出路,请标注你是使用哪一版本,方便我们批发作业 7.1-2 :返回是r //不是r-1
7.1-1 :略 如果遇到中英版有出路,请标注你是使用哪一版本,方便我们批发作业 7.1-2 :返回是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;返回(p+r)/2，如果小于且low>(p+r)/2，返回为low,否则返回为high. i p r 1 3 4 5 5 5 5 15 (p+r)/2

20 7.2.2 当A中元素都相等时，PARTITION算法中第4行总满足，将n个数划分成1和n-1两部分，此时快排运行时间为Ω(n^2)
7.4.2 最优情况下：递归式 根据主定理求解Ω(nlgn) 7.4.3 略

21 end THANKS