基本定义

• 什么是不稳定匹配：

  • A与b配对，但A更偏向于a；
  • B与a配对，但B更偏向于b。

• 完美匹配：每一个人都被匹配，且一一对应

稳定匹配：

对于经过匹配之后的任意a, b满足以下条件：

• 相对于b，a一定更喜欢当前跟他配对的对象
• 相对于a，b一定更喜欢当前跟他配对的对象

稳定匹配问题算法：

给定n个男人和n个女人的偏好表，来找出对应的稳定匹配组合。

GS算法：

初始化所有人都是单身的
while(如果有男人是单身，同时没有向每一个女人求婚){
   选择这样一个男人m
   w = m的喜好列表中的第一位还没有被求婚的
   if (w is free)
      匹配m和w
   else if (w 比起现有的配对对象m'，更偏好于m)
      匹配m和w，m'设置为单身
   else
      w 拒绝 m
}

该算法最多需要$n^{2}$次，即可终止

证明是否能够达到完美匹配：

• 假设有一名男性A没有完成匹配到任何女性
• 那么也有一名女性B没有完成匹配
• 即B从未被求婚过
• 但是A向所有女性都求过了一遍，所以该假设不成立。 ’

性质：

• 所有的男性和女性都能够得到匹配 假设在算法结束时，Z没有得到匹配。那么必然也存在一个女性A也没有得到匹配。若A没有得到匹配，则说明其从未被求过婚。但Z必然向每一个女性都求过婚，否则无法结束循环，故与假设相矛盾。
• 无不稳定配对
  • 假设存在一个不稳定因素：m和w匹配在一起，m’和w‘匹配在一起，但m更喜欢w’，w更喜欢m’。
  • Case1：m向w’求过婚，则一定被w’拒绝，即w’更喜欢m’，而不是m，与假设相矛盾
  • Case2：m没有向w‘求过婚，则m一定更喜欢当前的对象w，与假设相矛盾。
• 算法的执行总会得到一个相同结果 证明：
  • 有效伴侣：若m和w出现在了某个稳定匹配S中，那么w是m的有效伴侣。
  • 最佳伴侣：若女孩w是男孩m的偏爱列表上排名最高的有效伴侣，则w是m的最佳伴侣。 特点：GS算法是man-optimality的——每一个男人都会得到其最好的有效伴侣，即最佳伴侣。 证明：
  • 设Y是第一个被他的最佳有效伴侣拒绝的男人，A是拒绝Y的那个女人。
  • 设S是一个假设存在的稳定匹配：因为在定义上，A是Y的有效伴侣，故一定存在一个S，其中A和Y是配对的。
  • 当Y被A拒绝时，说明在A的偏好列表中，A更偏向于另一伴侣Z。
  • 当Y被A拒绝之前，Z没有被拒绝过。那么假设在存在的稳定匹配S中，Z也有一个伴侣B
  • 若Z向A求婚了，则说明A的排名要高于Z的另一可能伴侣B
  • 那么则说明（A,Z）在S中构成了不稳定对，因此产生了矛盾。 同时我们也得以证明了：GS算法的执行总会得到同一个结果。
• GS算法中女性总是会得到其最差的选择：
  • 假设在$S^{*}$中A和Z匹配，但Z不是A的最差有效伴侣。
  • 存在一种稳定匹配S，使得Y和A配对，同时A更加喜欢Z。
  • 在稳定匹配S中，Z和B配对，则根据man-optimality，Z会喜欢A多于B。
  • 则会造成在匹配S中，Z与A会私奔，与假设相矛盾。

典型例题

医生分配问题

即不同男女数量的稳定匹配问题 假设：有m所医院，n个医生，要把n个医生分配到m个医院中。(m < n)医院岗位没有空余，但医生可能没有工作。 稳定条件：不存在以下条件之一：

• s被分配到h，s’被分配到h’。h更喜欢s‘，s’也更喜欢h。
• s被分配到h，s’没有被分配，h更喜欢s‘而不是s

核心思想：应该让医院反转过来获取主动选择的权利、 伪代码：

while (存在某所医院有空余岗位){
  h 给它期望清单上排名最高的医生发offer
  if (该医生处于free状态)
      让该医生就职
  else if (这个医生已在h'处就职)
       if(该医生更喜欢h’)
           继续在h‘任职
        else 
           转到h任职
}

船只停泊问题

（如何将其他问题转化为稳定匹配问题） 背景： 假设某家公司有n个港口和n条船，且存在一个表，标明了m天中，每一天里每条船的状态，且在这m天中，每条船访问每个港口恰好一天。但是船可能需要维修或者保养，公司现在对每条船，当它到达某个港口时，公司可能会让它停留在这个港口维护，直到m天过去。 那么是否总是存在某种方案使得不会有两条船停在同一个港口（一个港口只能停一条船）？

基本思想： 关键在于转化处港口和船只之间的喜好排名表。

• 让船只访问各个港口的时间次序转化为对于各个港口的喜好排名
• 让港口被各个船只访问的时间次序的逆序转化为对于各个船只的喜好排名

可行性证明： 假设已经经过一次稳定匹配后，船只S停靠在港口P检修，但是出现了另一条船S’进港口P。 那么说明，对于港口P，其对于船只S‘的喜好程度大于S；对于S’，其应该更喜欢P，而不是其应该检修的港口P‘。存在不稳定因素，与假设相矛盾。

大O的定义：

上界：

若说f(n)是O(g(n))的，则存在c>0，$n_{0}$ >= 0，对于所有的n >= $n_{0}$，都有0 <= f(n) <= c * g(n)。 ![[Pasted image 20260302172000.png|245]]

O(g(n))实际上是函数的集合 大O的性质：

• 自反性：f 是O(f)
• 不变性：若f是O(g)，同时c > 0，那么cf 是O(g)
• 相乘性：若$f_{1}$是O($g_{1}$)，$f_{2}$是O($g_{2}$)，那么有$f_{1}f_{2}$是O($g_{1}g_{2}$)
• 传递性：若f是O(g)，g是O(h)，那么有f是O(h)
• 相加性：若$f_{1}$是O($g_{1}$)，$f_{2}$是O($g_{2}$)，那么有$f_{1} + f_{2}$是max{$g_{1},g_{2}$}

下界

若说f(n)是$\Omega(g(n))$，即存在常数c > 0和$n_{0}$ >= 0，使得对于所有的n >= $n_{0}$，都有f(n) >= c * g(n) >= 0 ![[Pasted image 20260302173315.png|249]]

紧邻边界

若说f(n)是$\theta(g(n))$，即存在常数$c_{1} > 0, c_{2}>0， n_{0}> 0$，满足： 0 <= $c_{1}$ * g(n) <= $c_{2}$ * g(n)对于所有n >= $n_{0}$成立 Ex: 对于f(n) = 32$n^{2} + 17n + 1$，可以说f(n) = O($n^{3}$)，但不能说f(n) = $\theta (n^{3})$

从极限角度理解： ![[Pasted image 20260302174818.png]]

NOTE：n!的复杂度等同于$2^{\theta(nlog n)}$ 证明： 两边同时取对数，有 $log^{(n!)} = log^{\sqrt{2\pi n}(\frac{n}{e})^{n}} = log^{\sqrt{2\pi n}} + nlog^{\frac{n}{e}}$