Problem 1 (教材习题 2.3-3)

使用数学归纳法证明：当 $n$ 刚好是 $2$ 的幂时，以下递归式的解是 $T(n) = n\log n$。

$T(n) = \begin{cases}$
2 & \text{if } n = 2 \
2T(n / 2) + n & \text{if } n = 2^k, k > 1
\end{cases}

Solution

基础情况：$n = 2$ 时，$T(2) = 2 = 2 \cdot \log 2$ 显然成立。

注：算法分析当中的 $\log$ 默认表示以 $2$ 为底的对数。

归纳步骤：假设 $n / 2$ 时，结论成立。考虑 $n$ 的情况。

$\begin{aligned}$
T(n) & = 2T(n / 2) + n = 2 \cdot \frac{n}2 \log {\frac{n}2} + n \
& = n(\log n - 1) + n \
& = n \log n
\end{aligned}

综上，在 $n$ 为 $2$ 的幂时， $T(n) = n\log n$ 。

Problem 2 (教材习题 2.3-5)

回顾查找问题（参见练习1-1问题1），注意到，如果序列 $A$ 已经排好序，就可以将该序列的中点与 $v$ 进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。 二分查找 算法重复这个过程，每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明：二分查找的最坏情况运行时间为 $\Theta(\log n)$ 。

Solution

上述伪代码是二分查找的递归版本，但如果知道“尾递归”这个概念的话，你应该能够很容易写出和它等价的迭代版本。实际编程的时候更推荐迭代版本，因为函数调用的开销要比单纯控制流转移来地大。不过递归版本更容易证明正确性。

算法1是一个典型的分治算法，记输入规模 $n$ 时的运行时间为 $T(n)$ ，分析代价如下：

• 分：计算中点并比较，代价为常数 。

• 治：递归调用，递归地处理左半边或者又半边，代价为 $T(n/2)$ 。

• 合：“治”的结果即时最终结果，代价为常数 。

于是， $T(n) = T(n / 2) + c$ ， $c$ 为常数，不难得出 $T(n) = \Theta(\log n)$ 。

Problem 3 (教材习题 2.3-6)

注意到第1讲PPT第9页（教材2.1节）中过程 $INSERTION-SORT$ 的第5-7行的 while 循环采用一种线性查找来（反向）扫描已排好序的子数组 $A[1..j-1]$ 。我们可以使用二分查找（参见练习1-2问题2）来把插入排序的最坏情况总运行时间改进到 $\Theta(n\log n)$ 吗？

Solution

二分查找并不能改进插入排序的最坏情况运行时间。

二分查找可以帮助我们以对数时间找到需要插入的位置，但我们插入的时候，依旧需要把插入位置后面的元素整体右移一位，这个操作仍然是线性时间的。因此总体的最坏情况运行时间受到了拷贝操作的制约，依旧是 $\Theta(n^2)$ ，提升查找操作的速度并没有撼动拷贝操作的数量级。

Problem 4 (教材习题 2.3-7)

描述一个运行时间为 $\Theta(n\log n)$ 的算法，给定 $n$ 个整数的集合 $S$ 和另一个整数 $x$ ，该算法能确定 $S$ 中是否存在两个其和刚好为 $x$ 的元素。

Solution

其实这一题可以用哈希表的方法得到 $\Theta(n)$ 复杂度的算法，不过这里为了教学目的，给出紧密结合第一讲内容的 $\Theta(n\log n)$ 的算法。

算法第1行排序的运行时间为 $\Theta(n\log n)$ ，第4-12行循环的运行时间为 $\Theta(n)$ ，整体时间依旧是 $\Theta(n \log n)$ （低阶项不影响数量级）。

算法的正确性可以通过循环不变式来证明。第4-12行 while 循环保持的不变式是：每次迭代开始前， 只可能 存在 $i \le p < q \le j$ 使得 $S[p] + S[q] = x$ 。

• 初始化：第一次迭代开始前， $i = 1, j = n$ ，不变式显然成立。

• 保持：迭代开始前，只可能存在 $i \le p < q \le j$ 使得 $S[p] + S[q] = x$ 。算法第5-11行分如下三种情况讨论：

  1. 如果 $S[i] + S[j] < x$ ，那么 $\forall i = p < q \le j, S[p] + S[q] < x$ ，于是只可能存在 $i + 1 \le p < q \le j$ 使得 $S[p] + S[q] = x$ ，从而 $i = i + 1$ 保持了不变式；

  2. 如果 $S[i] + S[j] > x$ ，那么 $\forall i \le p < q = j, S[p] + S[q] > x$ ，于是只可能存在 $i \le p < q \le j - 1$ 使得 $S[p] + S[q] = x$ ，从而 $j = j - 1$ 保持了不变式；

  3. 如果 $S[i] + S[j] = x$ ，迭代终止。

• 终止：当迭代终止的时候，有两种情况：

  1. 通过第10行的返回真终止，由于我们找到了 $S[i] + S[j] = x$ ，因此算法结果显然正确；

  2. 通过第4行循环条件不满足而终止，此时 $i = j$ ，根据循环不变式， 只可能 存在 $i \le p < q \le j$ 使得 $S[p] + S[q] = x$ ，但是现在 $i = j$ ，从而根本不存在这样的 $p$ 和 $q$ 。因此算法第13行返回假也是正确的。

综上，我们借助循环不变式证明了算法2的正确性。

这里补充一下两数之和问题的力扣链接，读者可以自行编程并提交评测。