国家互联网信息办公室|优秀程序员必会算法之延迟认可算法( 二 )


下面我们来看一下算法的稳定性:
1、随着轮数的增加 , 总有一个时候所有人都能配对 , 因此不会出现无法终止一直循环的情况 。
2、由于在每一轮中 , 至少有一个男性向某个女性告白 , 因此总的告白次数将随着轮数的增加而增加 , 倘若这个流程一直没有因所有人都配上对了而终止 , 最终必然会出现某个男性追遍了所有女性的情况 , 而一个女性只要被人追过一次 , 以后就不可能单身了 。 既然所有女性都被这个男性追过 , 那么就说明所有女性现在都不是单身 , 也就是说此时所有人都已配对 。
3、随着轮数的增加 , 一个男性追求女性的对象总是越来越糟 , 但一个女性的男友只可能变得越来越好 。 假设男 A 和女 1 各自有各自的对象 , 但比起现在的对象 , 男 A 更喜欢女 1 , 因此男 A 之前肯定向女 1 表白过 , 既然女 1 最后没有跟男 A 在一起 , 那么说明女 1 拒绝了男 A , 也即说明女 1 有了比男 A 更好的男性 。
这就证明了 , 两个人虽然不是一对 , 但都觉得对方比自己现在的伴侣好的情况绝不会发生 。
这个问题是数学界认真研究过的问题 , 但是相关理论最终给出的结果却很有意思 , 结果显示 , 对于传统的求爱过程来说 , 男性能够得到尽可能好的心上人 , 女性却不然 。 或者这也就是目前北上广深等大城市里面大龄剩女如此的多的原因 。

事实上 , 稳定婚姻的搭配往往不止一种 , 然而上述算法的结果可以保证 , 每一位男性得到的伴侣都是所有可能的稳定婚姻搭配方案中最理想的 , 同时每一位女性得到的伴侣都是所有可能的稳定婚姻搭配方案中最差的 。
因此 , 这个算法告诉我们:要主动出击 , 不能守株待兔 。
聪明的读者 , 你学会了吗?欢迎关注活在信息时代哦~