CS 170 2023年秋季 作业2

我们比较两个列表的中间元素（如果 \(k\) 是奇数；当 \(k\) 为偶数时需要稍加小心——见伪代码）。如果第一个列表的中间元素小于第二个列表的中间元素，那么所求元素不可能在第一个列表的左半部分，也不可能在第二个列表的右半部分。如果第二个列表的中间元素更小，则情况相反。因此我们可以截去这些元素，并在两个新数组上递归。

当每个列表的大小都为 1 时，\(k=1\)，只需比较两个元素并返回较小的那个。

为处理 \(k\) 为偶数的情况，以下给出伪代码，并基于伪代码写出正确性证明。未考虑 \(k\) 为偶数及取整问题的同学，只要主要思路正确，仍可获满分。

伪代码

procedure TwoArraySelection(a[1..k], b[1..k], k)
Let ℓ1 = ⌊k/2⌋ and ℓ2 = ⌈k/2⌉
while a[ℓ1] ≠ b[ℓ2] and k > 1 do
    if a[ℓ1] > b[ℓ2] then
        Set a := a[1, ···, ℓ1]; b := b[ℓ2+1, ···, k]; k := ℓ1
        Let ℓ1 = ⌊k/2⌋ and ℓ2 = ⌈k/2⌉
    else
        Set a := a[ℓ1+1, ···, k]; b := b[1, ···, ℓ2]; k := ℓ2
        Let ℓ1 = ⌊k/2⌋ and ℓ2 = ⌈k/2⌉
if k = 1 then
    return min(a[1], b[1])
else
    return a[ℓ1]

正确性证明 设 \(s_k\) 为我们寻找的元素。算法首先比较 \(a[ℓ_1]\) 与 \(b[ℓ_2]\)。假设 \(a[ℓ_1] > b[ℓ_2]\)。

那么在 \(a\) 与 \(b\) 的并集中，最多只有 \(k-2\) 个元素比 \(b[ℓ_2]\) 小，即 \(a[1,\cdots,ℓ_1-1]\) 和 \(b[1,\cdots,ℓ_2-1]\)，因此必有 \(s_k > b[ℓ_2]\)。类似地，所有元素 \(a[1,\cdots,ℓ_1]\) 和 \(b[1,\cdots,ℓ_2]\) 都小于 \(a[ℓ_1+1]\)；但这些共有 \(k\) 个元素，因此必有 \(s_k < a[ℓ_1+1]\)。

这表明 \(s_k\) 必包含在子数组 \(a[1,\cdots,ℓ_1]\) 与 \(b[ℓ_2+1,\cdots,k]\) 的并集中。特别地，由于我们丢弃了 \(ℓ_2\) 个小于 \(s_k\) 的元素，\(s_k\) 将是这个并集中第 \(ℓ_1\) 小的元素。

然后我们在此更小的问题上递归来找 \(s_k\)。\(a[ℓ_1] < b[ℓ_2]\) 的情况是对称的。

若我们在 \(a[ℓ_1]=b[ℓ_2]\) 之前达到 \(k=1\)，可提前终止递归，直接返回 \(a\) 与 \(b\) 中的最小元素。也可不用此判断，但处理基本情况会更繁琐。

或者，若到达 \(a[ℓ_1]=b[ℓ_2]\) 的状态，则恰好有 \(k\) 个更大的元素，因此 \(s_k = a[ℓ_1] = b[ℓ_2]\)。

运行时间分析 每一步都将考虑的元素数量减半，因此算法在 \(\log k\) 次递归调用后终止。假设比较操作花费常数时间，算法运行时间为 \(\Theta(\log k)\)。

（为何期望运行时间为 \(\Theta(\log k)\)？列表是有序的，一次比较就能排除常数比例的元素，类似于二分搜索。作为下界，一次比较只能提供 1 比特信息，而有 \(2k\) 种可能，因此需要 \(\Omega(\log k)\) 比特来区分。）

替代解法 注意到对于给定元素 \(A[i]\)，我们可通过将其与 \(B[k-i]\) 和 \(B[k-i+1]\) 比较，在 \(O(1)\) 内确定答案在 \(A[i]\) 之前还是之后。假设所求元素在 \(A\) 中，进行如下二分搜索。设 \(A[m]\) 是数组中间元素，若 \(B[k-m] < A[m] < B[k-m+1]\)，则答案为 \(A[m]\)。若 \(A[m] > B[k-m+1]\)，则在 \(A\) 的左半部分递归。若 \(A[m] < B[k-m]\)，则在右半部分递归。

若搜索在 \(A\) 上未成功，则在 \(B\) 上重复相同策略。

正确性：当 \(B[k-m] < A[m] < B[k-m+1]\) 时，\(A[m]\) 在并集中的排名为 \(m + k - m = k\)。若 \(B[k-m] > A[m]\)，则 \(A[m]\) 之前少于 \(k\) 个元素，答案在右半部分。若 \(B[k-m+1] < A[m]\)，则 \(A[m]\) 之前多于 \(k\) 个元素，答案在其左侧。

运行时间分析：二分搜索每一步需要 \(O(1)\) 次比较，然后在半个数组上递归。因此运行时间为 \(O(\log n)\)。

我们将数组分成两半，递归地计算 \(m = 0, 1, 2\) 时的 \(\text{num\_odd}[m]\) 和 \(\text{num\_even}[m]\)。这些分别表示元素和模 3 余 \(m\) 的奇数大小和偶数大小子集的个数。合并时，我们考虑左右子问题的所有 \(6 \times 6\) 对值，并将它们加到正确的条目中。最终输出为 \(\text{num\_odd}[0]\)。

合并步骤中计算 \(\text{num\_odd}\) 数组的伪代码

Initialize num_even[m] and num_odd[m] to 0 for m = 0, 1, 2
for i = 0, 1, 2 do
    for j = 0, 1, 2 do
        m ← (i + j) mod 3
        num_odd[m] ← num_odd[m] + left_num_even[i] * right_num_odd[j]
        num_odd[m] ← num_odd[m] + left_num_odd[i] * right_num_even[j]

我们可用 \(O(1)\) 次算术运算类似地计算 \(\text{num\_even}\)。

运行时间分析 合并步骤有 \(O(1)\) 次乘法和加法。对于大小为 \(k\) 的子问题，每次操作花费 \(O(k \log k)\) 时间。由于我们在每一层都分成两半，运行时间由以下递推式给出： \[T(n) = 2T(n/2) + O(n \log n)\] 展开递推式： \[T(n) = 2T(n/2) + cn \log n\] \[= \sum_{i=1}^{\log n} 2^i \cdot c(n/2^i) \log(n/2^i)\] \[\le \sum_{i=1}^{\log n} 2^i \cdot c(n/2^i) \log n\] \[= \sum_{i=1}^{\log n} cn \log n\] \[= cn(\log n)^2\] （其中 \(c\) 为某常数）。因此，运行时间为 \(O(n(\log n)^2)\)。

观察：如果我们将玩家分成 \(m\) 个不相交的组，让每组执行一次任务，那么至少有 \(m-s\) 组会成功，我们可以排除这些组中的玩家。

策略：为了在每次迭代中淘汰至少一半的玩家，将他们分成 \(2s\) 组。对于任务成功的组，我们移除这些组，并将剩余的组分成两半形成新的组集。我们重复此过程，直到每组只剩一人，此时我们就知道他们是间谍。

运行时间分析：在第一次迭代中，有 \(2s\) 组执行任务。每组执行任务后，由于有 \(s\) 个间谍，最多 \(s\) 个任务失败，这意味着在将失败的组拆分后，我们最多又有 \(2s\) 组。

在每次迭代中，至少一半的玩家从组中被移除。因此我们在 \(O(\log(n/s))\) 次迭代后识别出间谍。所以所需的任务总数为 \(O(s \log(n/s))\)。

替代解法：将玩家分成两组，让每组执行一次任务。如果一组成功则丢弃这些玩家，如果一组失败则对该组递归使用相同策略，直到组大小为 1。

分析：画出递归树后，你会看到在第 \(i\) 层，最多 \(\min(2^i, s)\) 个任务会失败，这些节点会分支到下一层。最多有 \(\log n\) 层。因此，任务总数被以下界定： \[\sum_{i=1}^{\log n} \min(2^i, s) \le \sum_{i=1}^{\log s} 2^i + \sum_{i=\log s}^{\log n} s = O(s) + s(\log n - \log s) = O(s \log(n/s))\]

(a) 要测试玩家 \(x\) 是否为人类，我们询问其他 \(n-1\) 名玩家 \(x\) 的身份是什么。

断言：\(x\) 是人类当且仅当至少一半的其他玩家说 \(x\) 是人类。

理由：如果 \(x\) 是人类，剩余玩家中至少一半也是人类，因此无论狼人怎么做，至少一半的玩家会说 \(x\) 是人类。另一方面，如果 \(x\) 是狼人，剩余玩家中严格多于一半是人类，因此严格少于一半的玩家能谎称 \(x\) 是人类。

(b) 主要思路：寻找人类的分治算法将这群朋友分成两个（近似）相等的集合 \(A\) 和 \(B\)，并在 \(A\) 和 \(B\) 上递归调用算法：\(x = \text{human}(A)\) 和 \(y = \text{human}(B)\)，然后使用第 (a) 部分的过程检查 \(x\) 或 \(y\)，返回其中被识别为人类的一个。如果只剩一名玩家，则保证是人类，返回该玩家。

正确性证明：我们将证明，当给定 \(n\) 名玩家且其中大多数为人类时，算法返回一名人类。对 \(n\) 进行强归纳：

基础情况：如果 \(n=1\)，组中只有一名玩家且为人类，算法显然正确。

归纳假设：命题对 \(k < n\) 成立。

归纳步骤：将组分成 \(A\) 和 \(B\) 后，至少有一组中人类多于狼人。根据归纳假设，算法从该组正确返回一名人类，因此当对 \(x\) 和 \(y\) 调用第 (a) 部分的过程时，至少有一人被识别为人类。

运行时间分析：两次对 \(n/2\) 规模问题的调用，然后对返回的两名玩家与输入组中每个朋友进行线性时间比较：\(T(n) = 2T(n/2) + O(n) = O(n \log n)\)，由主定理得出。

给评分者注意：如第 (c) 部分的 \(O(n)\) 查询解答也应获得满分。

(c) 主要思路：将朋友分成若干对，对于每对，如果任一人说对方是狼人，则丢弃两名朋友；否则丢弃任意一人，保留另一名朋友。如果 \(n\) 为奇数，使用第 (a) 部分测试落单者是否为人类。如果是，则完成；否则在剩余至多 \(n/2\) 名朋友上递归。

正确性证明：在算法的每次遍历后，如果之前人类占多数，人类仍然占多数。为此，设 \(n_1, n_2, n_3\) 分别为两名都是人类、两名都是狼人、各有一人的配对数量。人类占多数意味着 \(n_1 > n_2\)。注意所有 \(n_3\) 对第三类配对都被丢弃，从每对 \(n_1\) 第一类配对中保留一名朋友。所以我们至多剩下 \(n_1 + n_2\) 名朋友，其中多数 \(n_1\) 是人类。可通过对此进行对 \(n\) 的强归纳转化为形式化的正确性证明。

运行时间分析：在大小为 \(n\) 的输入集上，算法的一次运行中，我们在 \(n\) 为奇数时花费 \(O(n)\) 工作量检查落单者是否为人类，并花费 \(O(n)\) 将剩余朋友配对并将候选集修剪至至多 \(n/2\) 名玩家。因此，运行时间由以下递推式给出： \[T(n) = T(n/2) + O(n) = O(n)\] 由主定理得出。

替代解法：随机选择一名玩家并使用第 (a) 部分检查其是否为人类，如果不是则重复此过程。由于至少一半玩家是人类，我们找到一名人类需要检查的期望玩家数为 \(O(1)\)。由于检查需要 \(O(n)\) 次查询，整体解法在期望意义下也使用 \(O(n)\) 次查询。

quick_select 实现

def quick_select(array, k):
    """
    Returns the k-th smallest element of the array.
    Args:
        array (List[int]): List of integers to select from.
        k (int): The order statistic to select (0 is the smallest, len(array)-1 is the largest).
    """
    # randomly pick a pivot
    v = random.choice(array)
    partition1 = []
    partition2 = []
    partition3 = []
    # assign each element to the appropriate partition
    for n in array:
        if n < v:
            partition1.append(n)
        elif n == v:
            partition2.append(n)
        else:
            partition3.append(n)
    # recurse on the partition which contains the k-th smallest element
    if k < len(partition1):
        return quick_select(partition1, k)
    elif k < len(partition1) + len(partition2):
        return v
    else:
        return quick_select(partition3, k - len(partition1) - len(partition2))

算法描述：随机选择枢轴 \(v\)，将数组划分为三个分区：partition1（\(<v\)）、partition2（\(=v\)）、partition3（\(>v\)）。若 \(k < |\text{partition1}|\)，则第 \(k\) 小元素在 partition1 中，递归查找；若 \(k < |\text{partition1}| + |\text{partition2}|\)，则枢轴即为答案；否则在 partition3 中递归，并将 \(k\) 减去前两个分区的长度。

正确性：划分后，partition1 中所有元素 \(< v\)，partition2 中所有元素 \(= v\)，partition3 中所有元素 \(> v\)。第 \(k\) 小元素（0 起始下标）必落在唯一确定的分区中，且在该分区内的相对顺序统计量保持不变（或在 partition3 中相应偏移）。递归在更小的数组上进行，基础情况为数组长度为 1 时直接返回唯一元素。

期望运行时间分析：随机选择枢轴时期望将数组划分为常数比例的两部分，期望递归深度为 \(O(\log n)\)，每层期望工作量为 \(O(n)\)，因此期望运行时间为 \(O(n)\)。详细分析参见 https://people.eecs.berkeley.edu/~vazirani/algorithms/chap2.pdf#page=11 。