算法导论 — 思考题8-4 水壶

（水壶）假设给了你$n$n个红色的水壶和$n$n个蓝色的水壶。它们的形状和尺寸都各不相同。所有红色水壶的容量都不一样多，蓝色水壶也是如此。而且，对于每一个红色水壶来说，都有一个对应的蓝色水壶，两者容量相等；反之亦然。
　　你的任务是找出所有的容量相等的红色水壶和蓝色水壶，并将它们配成一对。为此，可以执行如下操作：挑出一对水壶，其中一个是红色的，另一个是蓝色的，将红色水壶中倒满水，再将水倒入蓝色水壶中。通过这一操作，可以判断出这个红色水壶的容量是否比蓝色水壶的容量更多，或是两者一样多的。假设这样的比较需要花费一个单位时间。你的目标是找出一个算法，它能够用最少的比较次数来确定所有水壶的配对。注意，你不能直接比较两个红色或两个蓝色的水壶。
　　a. 设计一个确定性算法，它能够用$Θ(n^2)$Θ(n2)次比较来完成所有水壶的配对。
　　b. 证明：解决该问题算法的比较次数下界为$Ω(n{\rm lg}n)$Ω(nlgn)。
　　c. 设计一个随机算法，其期望的比较次数为$O(n{\rm lg}n)$O(nlgn)，并证明这个界是正确的。对你的算法来说，最坏情况下的比较次数是多少？
　　
　　解
　　a.
　　依次选取红色水壶，将当前的红色水壶与所有的蓝色水壶进行比较，从中挑出与当前红色水壶容量一样的蓝色水壶。下面给出该算法的伪代码。
　　
　　显然，输出数组$M$M是$<1, 2, …, n>$<1,2,…,n>的一个排列。$M[i]$M[i]表示第$i$i个红色水壶与第几个蓝色水壶配对。从伪代码可以看出，$M[i]$M[i]也表示第$i$i个红色水壶参与比较的次数，因为第$M[i]$M[i]个蓝色水壶是与第$i$i个红色水壶比较的最后一个蓝色水壶。因此，总的比较次数为
　　　　$\sum_{i=1}^{n}{M[i]} = \sum_{i=1}^{n}{i} = \frac{n(n+1)}{2}$∑i=1n​M[i]=∑i=1n​i=2n(n+1)​
　　因此，这一算法需要进行$Θ(n^2)$Θ(n2)次比较。
　　
　　b.
　　用决策树模型来证明。考虑一个简单的例子，$3$3个红色水壶为$<a, b, c>$<a,b,c>，$3$3个蓝色水壶为$<d, e, f>$<d,e,f>，决策树如下所示。
　　
　　在决策树中，每个叶结点都是可能的配对情况，每个非叶结点表示一次比较。如果红蓝水壶各有$n$n个，那么根据排列组合原理，可能的配对情况一共有$n!$n!种，也就是说决策树一共有$n!$n!个叶结点。假设该决策树的高度为$h$h，那么它最多包含$2^h$2h个叶结点。于是有
　　　　$n!≤2^h$n!≤2h
　　对该不等式两边取对数，得到$h≥{\rm lg}(n!)=Ω(n{\rm lg}n)$h≥lg(n!)=Ω(nlgn)。所以，解决水壶配对问题的算法的比较次数的下界为$Ω(n{\rm lg}n)$Ω(nlgn)。
　　
　　c.
　　按照题目意思，每一个红色水壶都有一个蓝色水壶与之容量相等。比较简单的一个想法是，将所有红色水壶按照容量由小到大进行排序，再将所有蓝色水壶按照容量由小到大进行排序，排序后处于相同位置的红色水壶和蓝色水壶一定是容量相等的。排序可以采用随机化的快速排序，期望时间复杂度为$O(n{\rm lg}n)$O(nlgn)。然而，这个想法违反了题目要求。因为题目只允许红色水壶与蓝色水壶进行比较，而不允许相同颜色的水壶进行比较。
　　为了满足题目要求，可以考虑对快速排序做出修改，详见下面的伪代码${\rm BOTTLE-MATCH-2}$BOTTLE−MATCH−2。每次调用${\rm BOTTLE-MATCH-2}$BOTTLE−MATCH−2，从红色水壶$R$R中随机选出一个$r$r，将$r$r与所有蓝色水壶$B$B比较，从而将蓝色水壶分为$3$3类：容量小于$r$r的蓝色水壶$B_{less}$Bless​，容量大于$r$r的蓝色水壶$B_{more}$Bmore​，容量等于$r$r的蓝色水壶$b$b。类似地，用蓝色水壶$b$b将红色水壶也分为$3$3类：容量小于$b$b的蓝色水壶$R_{less}$Rless​，容量大于$b$b的蓝色水壶$R_{more}$Rmore​，容量等于$b$b的蓝色水壶$r$r。红色水壶$r$r与蓝色水壶$b$b的容量相等，二者配成一对。再递归的调用${\rm BOTTLE-MATCH-2}(R_{less}, B_{less})$BOTTLE−MATCH−2(Rless​,Bless​)和${\rm BOTTLE-MATCH-2}(R_{more}, B_{more})$BOTTLE−MATCH−2(Rmore​,Bmore​)。
　　
　　该算法实际上是对两个数组进行快速排序，根据第7章对快速排序的分析，期望的比较次数为$O(n{\rm lg}n)$O(nlgn)。在最坏情况下，比较次数为$O(n^2)$O(n2)。