DAA Midterm Revision

重修此课喜提 60 元账单

Gale-Shapley

算法在 $(n - 1)^2 + 1$ 天内结束

习题 1

Girl
g1	b3	b5	b2	b1	b4
g2	b5	b2	b1	b4	b3
g3	b4	b3	b5	b1	b2
g4	b1	b2	b3	b4	b5
g5	b2	b3	b4	b1	b5

Boys
b1	g3	g2	g5	g1	g4
b2	g1	g2	g5	g3	g4
b3	g4	g3	g2	g1	g5
b4	g1	g3	g4	g2	g5
b5	g1	g2	g4	g5	g3

解题方法复习

习题 2

有 n 名男演员和 n 名女演员，其中，有 k 名高个男演员和 k 名金发女演员。每位男演员都更喜欢金发女演员，每位女演员都更喜欢高个男演员。请证明，在稳定匹配中，高个男演员会匹配金发女演员，矮个男演员会匹配非金发女演员。

题解

假设有稳定匹配 (b_矮个, g_金发)，由于男女数量相同，必定有 (b_高个, g_黑发)。但根据规则，高个更喜欢金发，所以 (b_高个, g_金发) 是 rogue copule，与稳定匹配矛盾。

习题 3

证明如果所有女生的偏好列表都相同，那么只存在唯一的稳定匹配。

假设有两组稳定匹配，A / B，有 (g, b)_A 和 (g, b')_B。由于所有女生的偏好列表相同，所以匹配完全由男生的偏好列表决定。若要让 g 能够与 b' 匹配，则必定所有女生都更喜欢 b' 而不是 b，这就导致在 A 中产生了 (g, b') 的 rogue couple，与 A 的稳定性矛盾。

习题 4

证明不存在任何一种匹配（无论是否稳定），使得所有男生都比使用 Gale-Shapley 算法时的匹配结果更好。

设有匹配，使得所有男生都获得了比 GS 更好的结果，这意味着每个男生都与他匹配列表中更高的女孩匹配了，所以至少有一个男生与在 GS 算法中拒绝过他的女生匹配。但根据 GS 的规则，算法结束时每个男生都无法与他偏好列表中更高位的女生配对，因为她一定在某个时刻拒绝了他，并跟她更喜欢的男生匹配。所以如果一定要让一个男生获得更好的匹配，那么必定要拆散已经存在的匹配，这就导致另一个男生无法得到他更喜欢的女生。

习题 5

在每个稳定婚姻问题的实例中，是否必定存在一个合适的匹配，其中包含一对 $(b, g)$，使得 $ b $ 在 $ g $ 的偏好列表中排名第一，且 $ g $ 在 $ b $ 的偏好列表中排名第一？

并不，考虑以下情况 (12 21 21 12)

B_1 -> (G_1, G_2)，B_2 -> (G_2, G_1) 和
G_1 -> (B_2, B_1)，G_2 -> (B_1, B_2)。

有稳定匹配 (B_1, G_1)，(B_2, G_2) 和 (B_1, G_2)，(B_2, G_1)。它们均不同时是双方的第一选择。

习题 6

考虑一个稳定婚姻问题的实例，其中存在一名男生 $ b $ 和一名女生 $ g $，使得 $ b $ 在 $ g $ 的偏好列表中排名第一，且 $ g $ 在 $ b $ 的偏好列表中排名第一。那么，在该实例的任何稳定匹配 $ M $ 中，配对 $ (b, g) $ 是否都属于 $ M $？

是的。设存在 M'，有稳定匹配 (b, g')，那么一定存在 (b', g)。但由于 g 与 b 都相互最喜欢，则导致 (b, g)是 rogue couple，与稳定性矛盾。

算法实例

function validateInput(
  boysPreferences: string[][],
  girlsPreferences: string[][]
): void {
  const n = boysPreferences.length;
  if (n !== girlsPreferences.length) {
    throw new Error("男孩和女孩的数量必须相等。");
  }

  const boys = new Set<string>();
  const girls = new Set<string>();
  for (let i = 0; i < n; i++) {
    boys.add(`b${i + 1}`);
    girls.add(`g${i + 1}`);
  }

  for (let i = 0; i < n; i++) {
    const boyPref = boysPreferences[i];
    if (boyPref.length !== n) {
      throw new Error(`男孩 b${i + 1} 的偏好列表长度必须等于总数。`);
    }
    const boyPrefSet = new Set(boyPref);
    if (
      boyPrefSet.size !== n ||
      !Array.from(boyPrefSet).every((g) => girls.has(g))
    ) {
      throw new Error(`男孩 b${i + 1} 的偏好列表不完整或包含重复。`);
    }

    const girlPref = girlsPreferences[i];
    if (girlPref.length !== n) {
      throw new Error(`女孩 g${i + 1} 的偏好列表长度必须等于总数。`);
    }
    const girlPrefSet = new Set(girlPref);
    if (
      girlPrefSet.size !== n ||
      !Array.from(girlPrefSet).every((b) => boys.has(b))
    ) {
      throw new Error(`女孩 g${i + 1} 的偏好列表不完整或包含重复。`);
    }
  }
}

function getIndex(id: string): number {
  return parseInt(id.substring(1)) - 1;
}

function findStableMatching(
  boysPreferences: string[][],
  girlsPreferences: string[][]
): Map<string, string> {
  validateInput(boysPreferences, girlsPreferences);

  const n = boysPreferences.length;
  const boyToGirl = new Map<string, string>();
  const girlToBoy = new Map<string, string>();
  const freeBoys: string[] = [];
  for (let i = 0; i < n; i++) {
    freeBoys.push(`b${i + 1}`);
  }

  // 预处理女孩的偏好排名
  const girlRankings = new Map<string, Map<string, number>>();
  for (let i = 0; i < n; i++) {
    const girl = `g${i + 1}`;
    const ranking = new Map<string, number>();
    for (let j = 0; j < girlsPreferences[i].length; j++) {
      const boy = girlsPreferences[i][j];
      ranking.set(boy, j);
    }
    girlRankings.set(girl, ranking);
  }

  while (freeBoys.length > 0) {
    const boy = freeBoys.shift()!;
    const preferences = boysPreferences[getIndex(boy)];

    for (const girl of preferences) {
      if (!girlToBoy.has(girl)) {
        // 女孩未匹配
        boyToGirl.set(boy, girl);
        girlToBoy.set(girl, boy);
        break;
      } else {
        const currentBoy = girlToBoy.get(girl)!;
        const ranking = girlRankings.get(girl)!;
        const currentRank = ranking.get(currentBoy)!;
        const newRank = ranking.get(boy)!;

        if (newRank < currentRank) {
          // 女孩更喜欢当前男孩
          boyToGirl.delete(currentBoy);
          girlToBoy.delete(girl);
          boyToGirl.set(boy, girl);
          girlToBoy.set(girl, boy);
          freeBoys.push(currentBoy);
          break;
        }
      }
    }
  }

  return boyToGirl;
}

const boysPreferences: string[][] = [
  ["g2", "g4", "g3", "g1", "g5"], // b1 的偏好
  ["g3", "g2", "g1", "g5", "g4"], // b2 的偏好
  ["g2", "g1", "g3", "g5", "g4"], // b3 的偏好
  ["g4", "g3", "g5", "g1", "g2"], // b4 的偏好
  ["g2", "g4", "g3", "g1", "g5"], // b5 的偏好
];

const girlsPreferences: string[][] = [
  ["b2", "b5", "b1", "b3", "b4"], // g1 的偏好
  ["b2", "b3", "b1", "b4", "b5"], // g2 的偏好
  ["b4", "b2", "b5", "b1", "b3"], // g3 的偏好
  ["b3", "b1", "b5", "b2", "b4"], // g4 的偏好
  ["b5", "b3", "b4", "b1", "b2"], // g5 的偏好
];

// 调用稳定匹配算法
const stableMatching = findStableMatching(boysPreferences, girlsPreferences);

// 输出匹配结果
console.log("稳定匹配结果：");
for (const [boy, girl] of stableMatching.entries()) {
  console.log(`${boy} ↔ ${girl}`);
}

Master Method

复习

$T(n) = 2T(n/2) + n^3$

$T(n) = T(9n/10) + n$

$T(n) = 16T(n/4) + n^2$

$T(n) = 7T(n/3) + n^2$

$T(n) = 7T(n/2) + n^2$

$T(n) = 2T(n/4) + \sqrt{n}$

1. 递归主导：$n^{\log_b a}$
2. 平衡：$n^{\log_b a} \log n$
3. 分治主导：$f(n)$ when $af(\frac{n}{b}) \leq cf(n)$ where $c < 1, n \rightarrow \infty$

Divide and Conquer

题解

习题 1

我们给定一个正整数数组 → $ A[1:n] $

找到满足 $ 1 \leq i \leq j \leq n $ 的索引，使得 $ A[j] - A[i] $ 最大。

朴素算法：
枚举所有可能的 $ (i, j) $ 组合，并计算 $ A[j] - A[i] $，然后选择其中的最大值
→ 该算法的时间复杂度为 $ O(n^2) $

改进方法：

• 使用 分治法 得到 $ O(n \log n) $ 时间复杂度的算法
• 进一步优化该算法，使其达到 $ O(n) $ 时间复杂度

1. 将数组递归的平分为两份
2. 递归找出左数组的最大差值
3. 递归找出右数组的最大差值
4. 找出左数组的最小值
5. 找出右数组的最大值
6. 计算右减左（跨中间点）的差值
7. 返回三者中的最大值对应的两个索引

习题 2

我们给定一个整数数组（可能包含负数） → $ A[1:n] $

找到满足 $ 1 \leq i \leq j \leq n $ 的索引，使得 子数组和 $ A[i] + A[i+1] + \dots + A[j] $ 最大。

朴素算法：
枚举所有可能的 $ (i, j) $ 组合，计算 子数组和 $ A[i] + A[i+1] + \dots + A[j] $，然后选择其中的最大值
→ 时间复杂度为 $ O(n^3) $

优化方法：

• 使用 分治法 得到 $ O(n \log n) $ 时间复杂度的算法
• 进一步优化该算法，使其达到 $ O(n) $ 时间复杂度

1. 将数组递归的平分为两份
2. 递归找出左侧数组的最大前缀和，最大后缀和，总和
3. 递归找出右侧数组的最大前缀和，最大后缀和，总和
4. 计算跨越最大合：左最大后缀和 + 右最大前缀和
5. 三者的最大值为左右合并数组的最大子数组和
6. 返回最大值对应的两个索引

合并数组的最大前缀和：左最大前缀 比 左总和 + 右最大前缀
合并数组的最大后缀和：右最大后缀 比 右总和 + 左最大后缀
前缀合：从第一个元素向后累加，[1], [1, 2], [1, 2, 3]
后缀合：从最后一个元素向前累加，[3], [2, 3], [1, 2, 3]

习题 3

我们给定一个包含任意对象的数组 $ A[1:n] $。如果某个对象 $ x $ 在 $ A[1:n] $ 中出现的次数 多于 $ n/2 $ 次，则称其为 多数元素（majority element）。

• 当 $ n = 10 $ 时，至少需要出现 6 次 才能成为多数元素
• 当 $ n = 17 $ 时，至少需要出现 9 次 才能成为多数元素
• 当 $ n = 1 $ 时，唯一的元素即为多数元素

显然，在 $ A[1:n] $ 中最多只能存在 一个 多数元素。

任务：设计 D&C 算法，判断 $ A[1:n] $ 是否包含多数元素。

1. 将数组递归的平分为两份
2. 找出左侧数组出现次数最多的元素
3. 找出右侧数组出现次数最多的元素
4. 如果左右两侧的多数元素相同，则返回该元素
5. 否则，计算两个元素在整个数组中出现的次数，返回出现次数较多的元素
6. 确保返回的元素在整个数组中出现的次数大于 $ n/2 $，否则返回 null

习题 4

我们给定一个长度为 $ n $ 的数列 $ a_1, a_2, \dots, a_n $，假设所有数都互不相同。我们定义一个 逆序对 为满足 $ i < j $ 且 $ a_i > a_j $ 的一对索引 $ (i, j) $。

我们最初将 逆序对计数 作为衡量两个排列之间差异程度的一个指标。然而，有人可能会认为这个度量过于敏感。因此，我们引入一个新的概念，称为 “显著逆序对”，即当满足：

$$
i < j \quad \text{且} \quad a_i > 2a_j
$$

的索引对 $ (i, j) $ 被称为 显著逆序对。

任务：设计一个 $ O(n \log n) $ 的 分治算法 来计算一个序列 $ a_1, a_2, \dots, a_n $ 中的显著逆序对的数量。

1. 将数组递归的平分为两份
2. 递归找出左侧数组的显著逆序对数量（左侧元素除以右侧元素大于 2）
3. 递归找出右侧数组的显著逆序对数量
4. 嵌套遍历左右数组，找出跨越中间点的显著逆序对数量
5. 此时可以使用排序算法加速

习题 5

最近点对问题（Closest pair of points in the plane）

我们有一个 平面点集：$\mathcal{P} = { p_1, p_2, \dots, p_n }$ 我们的目标是找到 距离最小的两点对。

朴素解法：

• 枚举所有点对，计算其距离，并找到最小距离。
• 该方法的时间复杂度为： $O(n^2)$

1. 将集合平均分为两份
2. 递归找出左侧集合中最近的两点对
3. 递归找出右侧集合中最近的两点对
4. 嵌套遍历左右集合，找出跨越中间点的最近两点对
5. 找出三者中的最小距离
6. 可以对 x 和 y 坐标分别排序，以加速查找

习题 6

有一个 n 节点的平衡完全二叉树，每个节点都有一个实数值且不重复。若节点 v 的值严格小于与其直接相连的所有节点的值，则节点 v 被称为 局部最小值。请设计一个 $O(\log n)$ 的算法来找到这个局部最小值。

1. 选择中间节点 m
2. 如果 m 是局部最小值，则返回 m
3. 否则，如果 m 的左侧节点更小，则递归左侧
4. 否则，递归右侧

题目并没有说明要找到全部局部最小值，所以不必遍历左右两侧子叶

如果需要找到全部局部最小值，可以使用以下方法：

1. 选择中间节点 m
2. 如果 m 是局部最小值，则跳过其左右子叶，直接进入子叶节点的下一层继续递归
3. 否则，分别递归左右两侧

但这样的时间复杂度为 $O(n)$