讨论 2

(i) 主思路

逆序对的数量可能达到二次级别，因此算法必须在不逐对检查的情况下确定总数。

思路是修改归并排序。将序列分成两半 \(n_1, \cdots, n_l\) 与 \(n_{l+1}, \cdots, n_k\)，在分别排序两半的同时统计每半内部的逆序对数；然后在合并两半时，统计两个数分别位于不同半区的逆序对 \((a_i, a_j)\) 的数量。总数等于这三部分之和。

(ii) 伪代码

procedure count(A)
    if length[A] = 1 then
        return A, 0
    B, x <- count(A 的前半部分)
    C, y <- count(A 的剩余部分)
    D <- 空列表
    z <- 0
    while B 非空或 C 非空 do
        if B 为空 then
            将 C 追加到 D 并移除 C 的元素
        else if C 为空 then
            将 B 追加到 D 并移除 B 的元素
        else if B[1] < C[1] then
            将 B[1] 追加到 D 并从 B 中移除 B[1]
        else
            将 C[1] 追加到 D 并从 C 中移除 C[1]
            z <- z + length[B]
    return D, x + y + z

(iii) 正确性证明

考虑合并过程中的某一步，假设指针分别指向 \(b_i\) 与 \(c_j\)。由于 \(B\) 和 \(C\) 已经有序，若将 \(b_i\) 追加到 \(D\)，不会产生新的逆序对，因为 \(b_i\) 小于 \(C\) 中剩余的所有元素，并且排在所有这些元素之前。

反之，若将 \(c_j\) 追加到 \(D\)，则 \(c_j\) 小于 \(B\) 中所有剩余元素，并且排在所有这些元素之后，因此逆序对的计数应增加 \(B\) 中剩余元素的个数。

(iv) 运行时间分析

在每次递归调用中，合并两个有序列表并计数耗时 \(O(n)\)。运行时间为 \(T(n) = 2T(n/2) + O(n)\)，由主定理（Master theorem）得 \(O(n \log n)\)。

(i) 主思路：

直觉上我们似乎要找出两个下标 \(i\) 和 \(j\)，使得子数组 \(A[i{:}j]\) 的和尽可能大，共有 \(O(n^2)\) 种可能。但存在分治解法：把 \(A\) 分成相等的两半 \(L\) 和 \(R\)，即 \(A[1{:}n/2]\) 与 \(A[n/2+1{:}n]\)。最大子数组有两种可能：

(a) 完全包含在 \(L\) 或 \(R\) 中：通过递归求解。令 \(s_1\) 为递归调用 \(L\) 的结果，\(s_2\) 为递归调用 \(R\) 的结果。

(b) 跨越边界（crosses the boundary），即起始于 \(L\)、终止于 \(R\)：若最大子数组为 \(A[i{:}j]\)，则 \(A[i, n/2]\) 必须是以 \(A[n/2]\) 结尾的最大子数组，且 \(A[n/2+1, j]\) 必须是以 \(A[n/2+1]\) 开始的最大子数组。看起来我们似乎需要求解两个最大子数组问题：找出使 \(A[i, n/2]\) 和最大的 \(i\)，以及使 \(A[n/2+1, j]\) 和最大的 \(j\)。注意每个问题都只需确定一个下标，各自只有 \(n/2\) 种可能，因此每个都可在 \(O(n)\) 步内完成。例如，为求 \(i\)，依次计算 \(A[k, n/2]\)（\(k = 1\) 到 \(n/2\)）并取最大值。最终令 \(s_3\) 为 \(A[i, n/2]\) 的元素和加上 \(A[n/2+1, j]\) 的元素和。

若 \(n = 1\)，返回 \(\max\{A[1], 0\}\)；否则返回 \(\max\{s_1, s_2, s_3\}\)。

(ii) 正确性证明：对 \(n\) 进行归纳。当数组长度为 \(1\) 时，算法显然正确。

当数组长度至少为 \(2\) 时，最大子数组有两种可能：

(a) 完全包含在 \(L\) 或 \(R\) 中。

(b) 跨越边界，即在第 \(n/2\) 个元素之前开始、在第 \(n/2\) 个元素之后结束。

第一种情况下，算法会输出 \(s_1\) 或 \(s_2\)，由归纳假设它们正确。

第二种情况下，跨越边界的最大子数组必须由“以第 \(n/2\) 个元素结尾的和最大的子数组”与“以第 \(n/2+1\) 个元素开始的的和最大的子数组”组成。因此该情况下算法输出 \(s_3\)，是正确的。

(iii) 运行时间分析：计算 \(s_3\) 的方法耗时 \(O(n)\)，因为每个 \(A[i{:}n/2]\) 与 \(A[n/2+1{:}i]\) 的和都可以在给定前一个和的情况下以 \(O(1)\) 时间算出。于是得到递推式：

\[ T(n) = 2T(n/2) + O(n) \]

由主定理可得运行时间为 \(O(n \log n)\)。

算法：将点按 \(x\) 坐标排序，令 \(L\) 为左半部分、\(R\) 为右半部分。对 \(L\) 和 \(R\) 分别递归，记返回的帕累托最优点集合分别为 \(L'\) 与 \(R'\)。通过一次线性扫描计算 \(R\) 中最大的 \(y\) 坐标 \(y_{\max}\)，然后移除 \(L'\) 中所有 \(y\) 坐标小于 \(y_{\max}\) 的点。返回 \(L'\) 与 \(R'\) 的并集。

证明：现在证明该算法在已按 \(x\) 坐标排序的点集上的正确性。最简单情况下只有一个点，它默认是帕累托最优的。设有多个点，则可假设 \(L'\) 包含 \(L\) 中的帕累托最优点，\(R'\) 包含 \(R\) 中的帕累托最优点。

\(R'\) 中的每个点在 \(L \cup R\) 中都是帕累托最优的，因为 \(L\) 中所有点的 \(x\) 坐标都更小，无法破坏 \(R'\) 中点的帕累托最优性。

对于 \(L'\) 中的每个点，当且仅当其 \(y\) 坐标大于 \(y_{\max}\)（\(R\) 中最大的 \(y\) 坐标）时，它在 \(L \cup R\) 中才是帕累托最优的。因此，算法返回的集合在 \(L \cup R\) 中是帕累托最优的。

运行时间：由主定理，该算法运行时间为 \(T(n) = 2T(n/2) + O(n) = O(n \log n)\)。

(a) \(x \cdot y = e^{2\pi i \cdot 8/10}\)。它总是一个 \(10\) 次单位根（这是一般性质）。但因为 \(8/10 = 4/5\)，它也是 \(5\) 次单位根。

若 \(x = e^{2\pi i \cdot 6/10}\)，\(y = e^{2\pi i \cdot 7/10}\)，则乘积会“绕圈”（wind around），变为 \(e^{2\pi i \cdot 13/10} = e^{2\pi i \cdot 3/10}\)。

(b) 由 \(\omega^n = 1\)，代入等比数列求和公式：

\[ \sum_{k=0}^{n-1} \omega^k = \frac{\omega^n - 1}{\omega - 1} = \frac{1 - 1}{\omega - 1} = 0 \]

(c) (i) \(\omega = i,\, -i\)。

证法之一：两边平方得 \(\omega^4 = 1\)，故只需考虑 \(4\) 次单位根：\(e^{2\pi i \cdot 0/4},\, e^{2\pi i \cdot 1/4},\, e^{2\pi i \cdot 2/4},\, e^{2\pi i \cdot 3/4}\)，即 \(1,\, i,\, -1,\, -i\)。几何上，它们对应沿复平面单位圆走 \(0\)、\(1\)、\(2\)、\(3\) 个四分之一圈。其中平方为 \(-1\) 的是 \(i\) 与 \(-i\)。

(ii) \(\omega = e^{2\pi i \cdot 1/8},\, e^{2\pi i \cdot 3/8},\, e^{2\pi i \cdot 5/8},\, e^{2\pi i \cdot 7/8}\)。

类似地，两边平方得 \(\omega^8 = 1\)，故只需考虑 \(8\) 次单位根。但 \(\omega^4 \ne 1\)，因此 \(\omega\) 不能是 \(4\) 次单位根。那些不是 \(4\) 次单位根的 \(8\) 次单位根恰好是 \(e^{2\pi i \cdot 1/8},\, e^{2\pi i \cdot 3/8},\, e^{2\pi i \cdot 5/8},\, e^{2\pi i \cdot 7/8}\)，经验证它们均满足 \(\omega^4 = -1\)。

(i) 主思路：

若 \(A\) 只有一行，则直接扫描该行并输出其最小值。

否则，仅通过扫描第 \(m/2\) 行找到 \(A\) 的最小元素。设该元素位于第 \(j\) 列，则由于 \(A\) 是单调矩阵，第 \(m/2\) 行以上所有行的最小值必定位于第 \(j\) 列左侧，即位于子矩阵 \(A[1{:}m/2-1,\; 1{:}j-1]\) 中；第 \(m/2\) 行以下所有行的最小值必定位于第 \(j\) 列右侧。因此我们递归调用算法处理子矩阵 \(A[1{:}m/2-1,\; 1{:}j-1]\) 和 \(A[m/2+1{:}m,\; j+1{:}n]\)，分别找出第 \(1\) 到 \(m/2-1\) 行与第 \(m/2+1\) 到 \(m\) 行的最小值并输出。

(ii) 正确性证明：对 \(m\) 进行完全归纳（total induction）。

基础情况 \(m = 1\)：算法显式地找出并输出该单一行的最小值。

若 \(A\) 有多行，算法当然会找出并输出第 \(m/2\) 行的正确最小值。如前所论证，\(A\) 的第 \(1\) 到 \(m/2-1\) 行的最小值与子矩阵 \(A[1{:}m/2-1,\; 1{:}j-1]\) 的最小值相同，而第 \(m/2+1\) 到 \(m\) 行的最小值与子矩阵 \(A[m/2+1{:}m,\; j+1{:}n]\) 的最小值相同。由归纳假设，算法正确输出这些矩阵的最小值，连同上面的第 \(m/2\) 行一起，便找出并输出了 \(A\) 所有行的最小值。

(iii) 运行时间分析：

有两种分析方法。其一是显式统计每层递归的总步数。由于 \(m\) 在每一步递归中减半，共有 \(\log m\) 层递归。在每一层递归中，矩阵的列被分成两部分——分别属于左子矩阵与右子矩阵。而且，执行分割只需扫描单行全部元素，耗时 \(n\)。这意味着在任意递归层，所有子矩阵的列互不相交：若各子矩阵分别有 \(n_k\) 列，则 \(\sum_k n_k \le n\)。将这些矩阵再分割到下一层所需的总步数为 \(\sum_k n_k \le n\)。因此共有 \(\log m\) 层递归，每层总耗时 \(n\)，总计 \(n \log m\)。

更精确地，当 \(m = 1\) 时 \(\log m = 0\)，因此表达式应为 \(n(\log m + 1)\) 以正确处理基础情况。

对于“图示法”（proof by picture），考虑下图示意：灰色框代表每层递归中要求解的子矩阵，蓝线代表每层递归中扫描的行。可以看到每层递归中蓝线的总长度为 \(O(n)\)。

另一种分析方法是通过写出并求解递推关系（尽管这不是得分必需）。设 \(T(m, n)\) 为求解 \(m \times n\) 数组所需的步数。找到第 \(m/2\) 行的最小值耗时 \(n\)；若该行最小值位于第 \(j\) 列，则递归规模至多为 \(m/2 \times j\) 与 \(m/2 \times (n - j)\)。于是可写出递推式：

\[ T(m, n) \le T(m/2, j) + T(m/2, n - j) + n \]

它不像主定理中的标准形式，是“二维”的。猜测 \(T(m, n) \le n(\log m + 1)\)，并用对 \(m\) 的强归纳法证明。

基础情况：\(T(1, n) = n = n(\log 1 + 1)\)。

归纳步骤：

\[ \begin{aligned} T(m, n) &\le T(m/2, j) + T(m/2, n - j) + n \\ &\le j(\log(m/2) + 1) + (n - j)(\log(m/2) + 1) + n \\ &= n(\log(m/2) + 1) + n = n(\log m + 1) \end{aligned} \]