Problem 1 (教材习题 2-1)
(在归并排序中对小数组采用插入排序) 虽然归并排序的最坏情况运行时间为 Θ(nlogn) ,而插入排序的最坏情况运行时间为 Θ(n2) ,但是插入排序中的常量因子可能使得它在 n 较小时,在许多机器上实际运行得更快。因此,在归并排序中,当子问题变得足够小时,采用插入排序来使递归的叶 变粗 是有意义的。考虑对归并排序的一种修改,其中使用插入排序来排序排序长度为 k 的 n/k 个子表,然后使用标准的合并机制来合并这些字表,这里 k 是一个待定的值。
证明:插入排序最坏情况可以在 Θ(nk) 的时间内排序每个长度为 k 的 n/k 个子表。
表明在最坏情况下如何在 Θ(nlog(n/k)) 时间内合并这些子表。
假定修改后的算法的最坏情况运行时间为 Θ(nk+nlog(n/k)) ,要使修改后的算法与标准的归并排序具有相同的运行时间,作为 n 的一个函数,借助 Θ 记号, k 的最大值是什么?
在实践中,我们应该如何选择 k ?
Solution
插入排序一个长度为 k 的子表的时间是 Θ(k2) ,一共有 n/k 个子表,总时间是 Θ(kn⋅k2)=Θ(nk) 。
考虑第1讲PPT第36页(对应课本2.3.2节)的递归树,由于在子序列长度为 k 的时候开始不用归并排序,而改用插入排序,因此递归树的深度为 (logn+1)−(logk+1)=log(n/k) ,每层的合并代价依旧是 Θ(n) ,从而总合并代价为 Θ(nlog(n/k)) 。
Θ(nk+nlog(n/k))=Θ(n(logn+k−logk))=Θ(n(logn+k)) 。
因此,从渐近亿以上来看,本题的做法并不能从根本上改进归并排序的时间,只能在数据规模较小的时候凭借系数上的优势获得更快的运行效果。
- 实际情况中,我们常常是通过选取不同的 k 来进行测试,选择表现性能最好的 k 。不过,如果假设 k 是常数的话,且设总体代价为 c1nk+c2nlog(n/k) 的话,你也可以通过对 k 求导求极值点的方式来得到一个最优的常数 k 。
Problem 2 (教材习题 2-2)
(冒泡排序的正确性) 冒泡排序是一种流行但低效的排序算法,它的作用是反复交换相邻的未按次序排列的元素。
- 假设 A′ 表示 Bubble−Sort(A) 的输出。为了证明 Bubble−Sort(A) 正确,我们必须证明它将终止并且有:
A′[1]≤A′[2]≤...≤A′[n]
其中 n=A.length 。为了证明 Bubble−Sort 确实完成了排序,我们还需要证明什么?
下面两部分将证明上述不等式。
为第2-6行的 for 循环精确地说明一个循环不变式,并证明该循环不变式成立。你的证明应该使用第一讲中给出的循环不变式的证明结构。
使用第2问证明的循环不变式的终止条件,为第1-7行的 for 循环说明一个循环不变式,并证明该循环不变式成立;该不变式将使你能证明第1问中提出的不等式。你的证明应该使用第一讲中给出的循环不变式的证明结构。
冒泡排序的最坏情况运行时间是多少?与插入排序的运行时间相比,其性能如何?
Solution
我们还需要证明 A′ 中的元素依旧是原本 A 中的元素。而这一点是显然的,因为我们只是交换了原数组中的元素而已,所以最终得到的数组只是原数组的一个重新排列,自然依旧是原本的元素。
第2-6行 for 循环的不变式:每次迭代开始前,A[j..n] 中的最小元素为 A[j] 。
初始化:第一次迭代开始前, j=n ,不变式显然成立。
保持:若迭代开始前, A[j..n] 中的最小元素为 A[j] ,
如果 A[j−1]<=A[j] ,那么 A[j−1] 就是 A[j−1..n] 中最小的元素;
如果 A[j−1]>A[j] ,那么算法第4行会交换 A[j−1] 和 A[j] 中的元素,于是 A[j−1] 就变成了 A[j−1..n] 中最小的元素。
则下一次迭代开始前, A[j−1..n] 中的最小元素为 A[j−1] 。
终止:最后一次迭代结束后, j=i ,根据循环不变式,有 A[i] 是 A[i..n] 中的最小元素。
第1-7行 for 循环的不变式:每次迭代开始前,A[1..i−1] 是 A[1..n] 中前 i−1 小的元素从小到大排列。
初始化:第一次迭代开始前, i=1 ,不变式显然成立。
保持:若迭代开始前,A[1..i−1] 是 A[1..n] 中前 i−1 小的元素从小到大排列,由第2-6行 for 循环的不变式可知,算法第2-6行会使得 A[i] 是 A[i..n] 最小的元素,从而在下一次迭代开始前 A[1..i] 是 A[1..n] 中前 i 小的元素从小到大排列。
终止:最后一次迭代结束后,i=n ,根据循环不变式,有 A[1..n−1] 是 A[1..n] 中前 n−1 小的元素从小到大排列,于是 A[n] 必然是 A[1..n] 中的最大元素。
于是,A[1..n] 已经排好了序,第1问不等式得证。
第 i 次外层循环会导致内层循环运行 n−i 次,总次数为 i=1∑n−1(n−i)=Θ(n2) ,最坏和最好情况下都是如此。因此,在最坏情况下,冒泡排序和插入排序性能相当;在最好情况下,冒泡排序比插入排序慢。
Problem 3 (教材习题 2-3)
(霍纳(Horner)规则的正确性) 给定系数 a0,a1,...,an 和 x 的值,代码片段
实现了用于求值多项式
P(x)=k=0∑nakxk=a0+x(a1+x(a2+⋯+x(an−1+xan)⋯))
的霍纳规则。
借助 Θ 记号,实现霍纳规则的以上代码片段的运行时间是多少?
编写伪代码来实现朴素的多项式求值算法,该算法从头开始计算多项式的每个项。该算法的运行时间是多少?与霍纳规则相比,其性能如何?
考虑以下循环不变式:
在第2-4行 for 循环每次迭代的开始有
y=k=0∑n−(i+1)ak+i+1xk
把没有项的和式解释为等于 0 。遵照第1讲中给出的循环不变式证明的结构,使用该循环不变式来证明终止时有 y=k=0∑nakxk 。
- 最后证明上面给出的代码片段将正确地求由系数 a0,a1,...,an 刻画的多项式的值。
Solution
假设算术运算是常数项时间,由于第2-4行循环运行了 n+1 次,则整体运行时间为 Θ(n) 。
伪代码如下,运行时间依旧是 Θ(n) ,和霍纳规则性能相当。
我上面的算法已经做了一些优化,借助上一个循环中 xi 的值来计算下一个循环中 xi+1 的值。如果你实现的算法更加暴力,每次都从头计算 xi 的值的话,那么你的算法时间复杂度应该是 Θ(n2) ,性能劣于霍纳规则。
证明:
初始化:第一次迭代开始前, i=n,y=0 ,不变式显然成立。
保持:若迭代开始前, y=k=0∑n−(i+1)ak+i+1xk ,则算法第3行使得 y=ai+x⋅k=0∑n−(i+1)ak+i+1xk=k=0∑n−iak+ixk ,保持了不变式。
终止:最后一次迭代结束后, i=−1 ,根据循环不变式,有 y=k=0∑nakxk 。
由第3问结论可知: y=k=0∑nakxk=P(x) ,算法正确地求出了由系数 a0,a1,...,an 刻画的多项式的值。
Problem 4 (教材习题 2-4)
(逆序对) 假设 A[1..n] 是一个有 n 个不同数的数组。若 i<j 且 A[i]>A[j] ,则二元组 (i,j) 称为 A 的一个 逆序对(inversion) 。
列出数组 ⟨2,3,8,6,1⟩ 的 5 个逆序对。
由集合 {1,2,...,n} 中的元素构成的什么数组具有最多的逆序对?它有多少逆序对?
插入排序的运行时间与输入数组中逆序对的数量之间是什么关系?证明你的回答。
给出一个确定在 n 个元素的任何排列中逆序对数量的算法,最坏情况需要 Θ(nlogn) 时间。(提示:修改归并排序。)
Solution
- (2,1),(3,1),(8,6),(8,1),(6,1) 。
这里为了方便起见,用元素而不是下标表示。
具有最多逆序对的数组是: ⟨n,n−1,...,2,1⟩ ,任意两个元素都是逆序对,一共有 Cn2=2n(n−1) 个逆序对。
考虑插入排序算法(见第1讲PPT第9页,教材2.1节)第6行的拷贝操作为关键操作,以其操作时间作为算法的运行时间,则插入排序算法的时间是数组中逆序对数量的常数倍。
令 I(j)=∣{i∣1≤i<j≤n∧A[i]>A[j]}∣ ,则数组中逆序对的总数量为 i=1∑nI(i)=i=2∑nI(i) ,不难发现 I(1)=0 。
考虑算法第5到第7行的 while 循环会对于每一个 i<j 但是 A[i]>A[j] 的 i 都运行一次(因为 A[1..j−1] 已经排好序了),一共运行了 I[j] 次。
再考虑第1行到第8行的 for 循环对于 i 从 2 到 n 都运行了一次。
于是,一共需要进行 i=2∑nI(i)=i=1∑nI(i) 次拷贝操作,恰好是数组中逆序对的数量。假设每次拷贝操作的时间为常数,则总时间为数组中逆序对数量的常数倍。
算法伪代码如下:
该算法的核心思路是分而治之,先递归地计数左半边和右半边的逆序对,然后再借助前后都已经排好序的性质来计数跨越中点的逆序对(关键:算法第34行)。
上述算法只在归并排序原本算法之外添加了常数项时间的操作,因此该算法最坏情况依旧只需要 Θ(nlogn) 的时间。
这里补充一下逆序对计数问题的洛谷模版题链接,读者可以自行编程并提交评测。
注意数据规模,后10个测试样例数据较大,结果需要用64位整数来存,32位整数会溢出,导致WA。