期末考试要是考这么难的题，我悲痛欲绝，我只能爪巴。

本文形成期间，与 whk 同学讨论了许多题目的解法。在此致谢。

T1 (5pts)

请叙述下述算法的功能并分析时间复杂度。

算法 Compute
输入: 整数 $n$
输出: 整数

x=0
for i=1 to n do
   for j=1 to i do
       for k=1 to i+j do
           x=x+1
return x

解：算法的目的是求出$$\begin{aligned}\sum_{i=1}^n \sum_{j=1} ^ i \sum_{k=1} ^ {i+1} 1 &= \sum_{i=1}^n \sum_{j=1}^i (i+j) \\ &= \sum_{i=1} ^ n (\sum _ {j=1} ^ i i + \sum_{j=1} ^ i j) \\ &= \sum _{i=1} ^ n \left [ i ^ 2 + \frac{(i+1)i}{2} \right ] \\ &= \frac12 \sum_{i=1} ^ n (3 i ^2 + i) \\ &= \frac{n ^ 3 + 2 n^2 + n}{2}\end{aligned}$$

复杂度，由于执行次数最多代码的是 x=x+1 ，共执行了 $O(n^3)$ 次，故算法时间复杂度 $O(n ^3)$.

T2 (5pts)

令 $f, g$ 和 $h$ 为定义在正整数上的正实数函数。
假设 $f(n)=O(g(n))$，$g(n)=O(h(n))$，证明 $f(n)=O(h(n))$.

证：有常数 $N_1, c_1$ 使得 $\forall n > N_1, f(n) \leq c_1\cdot g(n)$. 又有常数 $N_2, c_2$ 使得 $\forall n > N_2, g(n) \leq c_2\cdot h(n)$.

于是，$\forall n > \max\{N_1, N_2\}$ 我们有$$f(n) \leq c_1 \cdot g(n) \leq c_1 c_2 \cdot h(n)$$

故 $f(n) = O(h(n))$.

T3 (5pts)

求解递归方程  $T(n)=2T(n/2)+n^4$ 其中 $k>0$ 是一个常数。

注意到 $n^4$ 多项式地大于 $n ^ {\log_2 2} = n$. 由 master 定理，$T(n) = O(n ^ 4)$.

T4 (15pts)

设计分治算法求解下述问题：
输入：一个有  $n$ 个元素的数组 $A$ 和一个有  $k$ 个位置的集合 $$S = \{p_1, \dots, p_k\},\qquad 1\leq p_1 < p_2 <\dots < p_k \leq n$$
输出：对于每个 $i\in \{1,\dots,k\}$，输出  $A$ 中第 $p_i$ 小的元组。
例如，如果 $k=1, S=\{i\}$ 对应元素中第  $i$ 小的元素，$k=2, S=\{1,n\}$ 对应找到数组中最小和最大的元素。
设计时间复杂度为 $O(n\log k)$ 的分治算法求解此问题，要求写出伪代码并证明算法的时间复杂度。

这题其实有点难下手。主要在于，需要恰当地理解那个 $\log k$ 是怎么来的。

如果 $k=1$，那我们会毫不犹豫地采用线性第 $n$ 大算法。现在，思考如何把这个算法扩展到 $k=2$ 上面去。做法如下：

  • 取一个值 $m$，把整个序列分为 $<m, \geq m$ 这两部分。
  • 如果第 $S_1, S_2$ 大的数都在同一侧，则只递归那一侧；
  • 如果在不同侧，则转化为两个区间第 $n$ 大问题。

不难注意到，上述算法的最坏情况是，在第一次递归时便产生分叉。此时的复杂度是：第一层最多有两个分叉；从第二层开始到最后一层，都是有两个子区间需要递归。于是总的复杂度：$$n + 2(n/2) + 2(n/4) + \cdots + 2 (n/n) = O(n)$$

现在把这个算法扩展到 $k$ 取任意值的情况。显然，最坏情况下，前 $\log k$ 层所有的子区间都需要递归；从第 $\log k$ 层开始，每层都只有 $\log k$ 个自区间需要递归。于是总复杂度是：$$n \cdot \log k +  \log k \cdot (1+2+4+\cdots + \frac{1}{2 ^ {\log k}} n) = O(n \log k)$$

伪代码如下。

def DIVIDE(A, S):
    mid <- DIVIDE(A, len(A)/2)
    
    le <- A 中小于 mid 的数
    kle <- S 中小于 len(le) 的数
    rt <- A 中不小于 mid 的数
    krt <- S 中还剩下的数，每个都减去 len(le)
    
    return DIVIDE(le, kle) + DIVIDE(rt, krt)

T5 (15pts)

要为将即将到来的哈尔滨世界博览会设计和生产 $n$ 个不同的展品，每一个项目首先用 CAD 软件设计，然后送到外面加工厂加工，第 $i$ 个展品的设计时间为 $d_i$，加工时间为 $f_i$. 加工厂能力很强，可以同时加工 $n$ 个展品，所以对于每件展品，只要设计结束就可以立刻开始加工。但是，只有一位设计师，所以需要确定产品设计的顺序，以最快时间完成所有 $n$ 件展品的设计和加工。比如，完成了第一件展品的设计，可以将其交给加工厂，然后立刻开始第二件展品的加工。当完成第二件展品的设计时，可以将其交给加工厂而不需要考虑是否第一件展品已经加工完成。
设计多项式贪心算法求解此问题，分析时间复杂度，并证明其正确性。

解：我们的策略是，按加工耗时排序，加工耗时越长的越早做。

证明如下： 由于加工是并行的，故每个任务的耗时仅仅取决于其开始设计的时间点。于是，我们交换相邻两个任务，对其余任务的完成时间无影响。接下来证明引理：对于相邻的两个任务，如果某任务的加工时间比另一任务长，那么我们应该把它放到前面做。

【引理】设有 $i,j$ 两任务，设计耗时分别为 $a_i, a_j$、加工耗时分别为 $b_i, b_j$，且 $b_i > b_j$. 那么，先做 $i$ 再做 $j$，比先做 $j$ 再做 $i$ 的总用时更低。前者的用时是：$$\text{Cost}_{ij} = \max \{ a_i + b_i, a_i + a_j + b_j \}$$后者的用时是：$$\text{Cost}_{ji} = \max \{ a_j+b_j, a_i+a_j + b_i \}$$

注意到 $\text{Cost}_{ji} \geq a_i+a_j + b_i $，而显然 $a_i+a_j + b_i  \geq a_i + b_i$；又因为我们有假设 $b_i > b_j$，故 $a_i+a_j + b_i  > a_i + a_j + b_j$，于是 $\text{Cost}_{ji} \geq a_i+a_j + b_i \geq  \text{Cost}_{ij}$，于是我们应该先做 $i$，再做 $j$. 引理证毕。

有了上述引理，我们就可以按照冒泡排序的方式，不断交换相邻的任务，直到按加工耗时从大到小排列为止。我们断言：在某个最优解中，对于每一对相邻的任务，前者的加工耗时必定比后者长（或者相等）。这形成了一个全序，于是这个任务序列是按照加工耗时从大到小排列的。

时间复杂度是按加工耗时排序的复杂度，也就是 $O(n\log n)$.

T6 (15pts)

我们考虑将数轴上的 n 个点聚成 k 类的问题。
输入：$n$ 个从小到大的不同实数 $x_1, x_2, \dots, x_n$ 表示 $n$ 个不同点，一个参数 $k\leq n$.
任务：将 $n$ 个点划分成 $k$ 个不相交的非空集合 $S_1, \dots, S_k$ 满足 $$\bigcup_{i=1}^k S_i = \{x_1, x_2, \dots, x_n\}$$ $S_i$ 中所有点在 $S_{i+1}$ 中所有点左边，$1\leq i < k$，也就是说对于任意 $x\in S_i, z\in S_{i+1}$，有 $x<z$.
目标：最小化$$\sum_{i=1}^k \text{cost}(S_i)$$其中 $\text{cost}(S_i)=(\max(S_i) - \min(S_i))^ 2$. $\max(S_i)$ 是  $S_i$ 中的最小元素，$\min(S _i)$ 是 $S_i$ 中的最大元素。

设计时间复杂度为 $O(n ^ 2k)$ 的动态规划算法，找到最优聚类。要求写出伪代码、递归方程并分析算法的时间复杂度。

解：记 $f(p,t)$ 表示 $x_1 , \cdots, x_p$ 分为 $t$ 个类时的代价，其中保证 $t\leq p$. 这个状态必然是从 $f(~ * ~ , t-1)$ 转移过来的。我们只需要决策最后一个划分点放在哪里即可。于是 $$f(p, t) = \begin{cases} \text{cost} \{x_1, x_2, \dots, x_p\}, & t=1 \\ \min_{1\leq a < p}\{  f(a, t-1) + \text{cost}\{ x_{a+1}, \dots, x_p \}\} & t\neq 1\end{cases}$$

计算 $f(p, t)$ 需要直接耗费 $O(p)$ 的代价。故总复杂度是 $O(n ^ 2 k)$.

def DP(p, t):
    if k == 0: return cost(x)
    
    res = +inf
    for a in [1, p]:
        res = min(res, DP(a, t-1) + cost(X[a...p]))
    return res

这里有一个细节：区间 cost 需要预处理出来，否则复杂度压不到 $O(n ^2k)$ 以内。