讨论课 1：渐近分析、递推关系与分治

(a) \[ \lim_{n \to \infty} \frac{n^3}{n^4} = \lim_{n \to \infty} \frac{1}{n} = 0 \] 因此 \(f(n) = O(g(n))\)。

(b) 令 \(f(n) = 3n\)，\(g(n) = 5n\)。则 \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = \frac{3}{5}\)，即 \(f(n) = \Theta(g(n))\)。由 \(\Theta\) 的定义，此时仍有 \(f(n) = O(g(n))\) 成立。

(c) 由洛必达法则： \[ \lim_{n \to \infty} \frac{\log n}{n^c} = \lim_{n \to \infty} \frac{n^{-1}}{c n^{c-1}} = \lim_{n \to \infty} \frac{1}{c n^c} = 0 \] 因此 \(\log n = O(n^c)\)。

(d) 令 \(f(x) = x(\sin x + 1)\)，\(g(x) = x\)。由于 \(\sin x + 1 \le 2\)，故对所有 \(x \ge 0\) 有 \(f(x) \le 2 \cdot g(x)\)，所以 \(f(x) = O(g(x))\)。

然而，若尝试计算极限： \[ \lim_{x \to \infty} \frac{x(\sin x + 1)}{x} = \lim_{x \to \infty} (\sin x + 1) \] 该极限不存在（正弦函数永远振荡）。

(a) \(f_3, f_7, f_2, f_5, f_4, f_9, f_8, f_6, f_1\)

(b) (i) \(f = \Theta(g)\)；利用对数换底公式，\(\frac{\log n}{\log 3}\) 与 \(\frac{\log n}{\log 4}\) 仅差一个常数因子。

(ii) \(f = O(g)\)；\(f(n) = 4n \log n\)，\(g(n) = 3n^2 \log n\)，\(g\) 中多项式次数更高。

(iii) \(f = \Omega(g)\)；任何多项式都支配对数乘积。亦可通过以下极限证明： \[ \lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{\sqrt{n}}{(\log n)^3} = \lim_{n \to \infty} \frac{\frac{1}{2\sqrt{n}}}{3(\log n)^2 \cdot \frac{1}{n}} \text{ [洛必达法则]} = \lim_{n \to \infty} \frac{\sqrt{n}}{6(\log n)^2} = \lim_{n \to \infty} \frac{\sqrt{n}}{24 \log n} \text{ [洛必达法则]} = \lim_{n \to \infty} \frac{\sqrt{n}}{48} \text{ [洛必达法则]} = \infty \]

(iv) \(f = \Theta(g)\)；\(f\) 和 \(g\) 都呈 \(\Theta(n)\) 增长，因为线性项主导了其他项。亦可通过以下极限证明： \[ \lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{n + \log n}{n + (\log n)^2} = \lim_{n \to \infty} \frac{1 + \frac{1}{n}}{1 + \frac{2 \log n}{n}} \text{ [洛必达法则]} = 1 \]

(a) 可以使用主定理！注意到 \(a = 2\)，\(b = 2\)，\(d = 1\)，有 \(\log_b a = \log_2 2 = 1 = d\)。因此由主定理： \[ T(n) = O(n^d \log n) = O(n \log n) \]

(b) 由于无法使用主定理，采用「展开」策略： \[ \begin{aligned} T(n) &= T(n-1) + n \\ &= (T(n-2) + (n-1)) + n \\ &= ((T(n-3) + (n-2)) + (n-1)) + n \\ &= \cdots \text{（继续展开）} \\ &= T(1) + 2 + 3 + \cdots + (n-2) + (n-1) + n \\ &= 1 + 2 + 3 + \cdots + (n-2) + (n-1) + n \\ &= \sum_{i=1}^{n} i \\ &= \frac{n(n+1)}{2} \\ &= O(n^2) \end{aligned} \]

(c) 继续展开！ \[ \begin{aligned} T(n) &= 3T(n-2) + 5 \\ &= 3^2 T(n-4) + 5 \cdot 3 + 5 \\ &= 3^3 T(n-6) + 5 \cdot 3^2 + 5 \cdot 3 + 5 \\ &= 3^4 T(n-8) + 5 \cdot 3^3 + 5 \cdot 3^2 + 5 \cdot 3 + 5 \\ &= \cdots \\ &= 3^{\lfloor n/2 \rfloor} T(n \bmod 2) + 5 \cdot 3^{\lfloor n/2 \rfloor - 1} + 5 \cdot 3^{\lfloor n/2 \rfloor - 2} + \cdots + 5 \cdot 3^2 + 5 \cdot 3 + 5 \\ &= 1 \cdot 3^{\lfloor n/2 \rfloor} + 5 \cdot 3^{\lfloor n/2 \rfloor - 1} + 5 \cdot 3^{\lfloor n/2 \rfloor - 2} + \cdots + 5 \cdot 3^2 + 5 \cdot 3 + 5 \\ &= 3^{\lfloor n/2 \rfloor} + 5 \cdot \frac{3^{\lfloor n/2 \rfloor} - 1}{3 - 1} \\ &= \frac{7}{2} \cdot 3^{\lfloor n/2 \rfloor} - \frac{5}{2} \\ &= O(3^{n/2}) \end{aligned} \]

(d) 使用递归树方法。节点表示一次递归调用所做的工作：

第 0 层：\(O(n \log n)\) 第 1 层：\(2\) 个节点，每个 \(O\left(\frac{n}{2} \log \frac{n}{2}\right)\)，合计 \(O\left(n \log \frac{n}{2}\right)\) 第 2 层：\(4\) 个节点，每个 \(O\left(\frac{n}{4} \log \frac{n}{4}\right)\)，合计 \(O\left(n \log \frac{n}{4}\right)\) \(\ldots\)

将各层相加： \[ \begin{aligned} T(n) &= O(n \log n) + O\left(n \log \frac{n}{2}\right) + O\left(n \log \frac{n}{4}\right) + \cdots + O(1) \\ &= O\left(\sum_{i=0}^{\lfloor \log n \rfloor} n \log \frac{n}{2^i}\right) \\ &= O\left(\sum_{i=0}^{\lfloor \log n \rfloor} n (\log n - i)\right) \\ &= O\left(n \left(\log^2 n - \sum_{i=0}^{\lfloor \log n \rfloor} i\right)\right) \\ &= O\left(n \left(\log^2 n - \frac{1}{2} \log^2 n\right)\right) \\ &= O(n \log^2 n) \end{aligned} \]

(i) 主要思路：若 \(A\) 只有 1 个元素，直接输出 1。否则，检查 \(A[N/2] < A[N/2 + 1]\) 是否成立。若成立，则递归调用算法于子数组 \(A[1 : N/2]\)。否则，递归调用算法于子数组 \(A[N/2 + 1 : N]\)（并将 \(N/2\) 加到答案上）。

(ii) 正确性证明：当 \(A\) 的大小为 1 时，算法正确，因为 \(j\) 唯一可能的取值就是 1。若 \(A[N/2] < A[N/2 + 1]\)，则我们知道 \(j \le N/2\)，因此 \(j\) 包含在我们递归调用的子数组中，可以归纳地假设递归调用找到了正确的下标。否则，我们知道 \(j > N/2\)，同样有 \(j\) 包含在递归调用的子数组中，并且可以归纳地假设递归调用找到了正确的下标（在加上 \(N/2\) 之前）。

(iii) 运行时间分析：算法花费 \(O(1)\) 时间比较 \(A[N/2]\) 与 \(A[N/2 + 1]\)。每次比较后我们将问题规模减半，因此从长度为 \(N\) 的数组到长度为 1 的数组需要 \(\log N\) 次递归调用。故总运行时间为 \(O(\log N)\)。

(a) \[ H_0 = [1] \] \[ H_1 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \] \[ H_2 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} \]

(b) \[ H_2 v = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ -1 \\ -1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 4 \end{bmatrix} \]

(c) \[ H_1(v_1 + v_2) = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \] \[ H_1(v_1 - v_2) = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 2 \\ -2 \end{bmatrix} = \begin{bmatrix} 0 \\ 4 \end{bmatrix} \] 我们观察到 \[ u = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 4 \end{bmatrix} = H_2 v \]

(d) \[ H_k v = \begin{bmatrix} H_{k-1} v_1 + H_{k-1} v_2 \\ H_{k-1} v_1 - H_{k-1} v_2 \end{bmatrix} = \begin{bmatrix} H_{k-1}(v_1 + v_2) \\ H_{k-1}(v_1 - v_2) \end{bmatrix} \]

(e) 计算 (d) 中描述的两个子问题，并按 (c) 的方式合并。设 \(T(n)\) 表示计算 \(H_k v\) 所需的操作数。我们需要求出向量 \(v_1 + v_2\) 和 \(v_1 - v_2\)，这需要 \(O(n)\) 次操作。我们还需要计算矩阵-向量乘积 \(H_{k-1}(v_1 + v_2)\) 和 \(H_{k-1}(v_1 - v_2)\)，各需要 \(T(n/2)\) 次操作。因此运行时间的递推关系为： \[ T(n) = 2T\left(\frac{n}{2}\right) + O(n) \] 使用主定理，得到 \(T(n) = O(n \log n)\)。