完美匹配：假設(shè)有N個男人和N個女人，如果男人和女人匹配結(jié)成一對，是為完美匹配 不穩(wěn)定匹配： 假設(shè)有兩對夫婦

那么如何證明這個算法的有效性呢？ 一，證明其為完美匹配： 用反證法，假如最后還余一個單身男性，那么自然以余下的一女子匹配了 二，證明其為最穩(wěn)定匹配： 用反證法，假如有兩個匹配（m1,w1）,(m2,w2)，m1更喜歡w2，w2更喜歡m1。然后由于m1更喜歡w2，所以m1必然向w2求過婚。假如w2拒絕的話，那么原因必然是存在一個她更喜歡的m*的存在。倘若W*存在的話，也論不到資格更低的w2的存在了。