Problem 1 (教材习题 2.3-3)
使用数学归纳法证明:当 n 刚好是 2 的幂时,以下递归式的解是 T(n)=nlogn。
T(n)={22T(n/2)+nif n=2if n=2k,k>1
Solution
基础情况:n=2 时,T(2)=2=2⋅log2 显然成立。
注:算法分析当中的 log 默认表示以 2 为底的对数。
归纳步骤:假设 n/2 时,结论成立。考虑 n 的情况。
T(n)=2T(n/2)+n=2⋅2nlog2n+n=n(logn−1)+n=nlogn
综上,在 n 为 2 的幂时, T(n)=nlogn 。
Problem 2 (教材习题 2.3-5)
回顾查找问题(参见练习1-1问题1),注意到,如果序列 A 已经排好序,就可以将该序列的中点与 v 进行比较。根据比较的结果,原序列中有一半就可以不用再做进一步的考虑了。 二分查找 算法重复这个过程,每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明:二分查找的最坏情况运行时间为 Θ(logn) 。
Solution
上述伪代码是二分查找的递归版本,但如果知道“尾递归”这个概念的话,你应该能够很容易写出和它等价的迭代版本。实际编程的时候更推荐迭代版本,因为函数调用的开销要比单纯控制流转移来地大。不过递归版本更容易证明正确性。
算法1是一个典型的分治算法,记输入规模 n 时的运行时间为 T(n) ,分析代价如下:
于是, T(n)=T(n/2)+c , c 为常数,不难得出 T(n)=Θ(logn) 。
Problem 3 (教材习题 2.3-6)
注意到第1讲PPT第9页(教材2.1节)中过程 INSERTION−SORT 的第5-7行的 while 循环采用一种线性查找来(反向)扫描已排好序的子数组 A[1..j−1] 。我们可以使用二分查找(参见练习1-2问题2)来把插入排序的最坏情况总运行时间改进到 Θ(nlogn) 吗?
Solution
二分查找并不能改进插入排序的最坏情况运行时间。
二分查找可以帮助我们以对数时间找到需要插入的位置,但我们插入的时候,依旧需要把插入位置后面的元素整体右移一位,这个操作仍然是线性时间的。因此总体的最坏情况运行时间受到了拷贝操作的制约,依旧是 Θ(n2) ,提升查找操作的速度并没有撼动拷贝操作的数量级。
Problem 4 (教材习题 2.3-7)
描述一个运行时间为 Θ(nlogn) 的算法,给定 n 个整数的集合 S 和另一个整数 x ,该算法能确定 S 中是否存在两个其和刚好为 x 的元素。
Solution
其实这一题可以用哈希表的方法得到 Θ(n) 复杂度的算法,不过这里为了教学目的,给出紧密结合第一讲内容的 Θ(nlogn) 的算法。
算法第1行排序的运行时间为 Θ(nlogn) ,第4-12行循环的运行时间为 Θ(n) ,整体时间依旧是 Θ(nlogn) (低阶项不影响数量级)。
算法的正确性可以通过循环不变式来证明。第4-12行 while 循环保持的不变式是:每次迭代开始前, 只可能 存在 i≤p<q≤j 使得 S[p]+S[q]=x 。
初始化:第一次迭代开始前, i=1,j=n ,不变式显然成立。
保持:迭代开始前,只可能存在 i≤p<q≤j 使得 S[p]+S[q]=x 。算法第5-11行分如下三种情况讨论:
如果 S[i]+S[j]<x ,那么 ∀i=p<q≤j,S[p]+S[q]<x ,于是只可能存在 i+1≤p<q≤j 使得 S[p]+S[q]=x ,从而 i=i+1 保持了不变式;
如果 S[i]+S[j]>x ,那么 ∀i≤p<q=j,S[p]+S[q]>x ,于是只可能存在 i≤p<q≤j−1 使得 S[p]+S[q]=x ,从而 j=j−1 保持了不变式;
如果 S[i]+S[j]=x ,迭代终止。
终止:当迭代终止的时候,有两种情况:
通过第10行的返回真终止,由于我们找到了 S[i]+S[j]=x ,因此算法结果显然正确;
通过第4行循环条件不满足而终止,此时 i=j ,根据循环不变式, 只可能 存在 i≤p<q≤j 使得 S[p]+S[q]=x ,但是现在 i=j ,从而根本不存在这样的 p 和 q 。因此算法第13行返回假也是正确的。
综上,我们借助循环不变式证明了算法2的正确性。
这里补充一下两数之和问题的力扣链接,读者可以自行编程并提交评测。