《算法导论》2.3-7 检查集合中是否存在两数字和为指定的X--算法和证明

浏览数：24 / 时间：2015年06月08日

习题2.3-7：设计一个算法，对于一个给定的包含n个整数的集合S和另一个给定的整数X，该算法可以在时间内确定S中是否存在两个元素，使得它们的和恰为X。

解题思路：首先应该想到的是先用一个的排序算法对S中的元素进行排序。接下来有两种处理思路，第一种思路是遍历已经排好序了的S中的所有元素a，并采用

二分查找的方法在S中查找X-a，如果能够找到，那么说明S中确实存在两个元素的和为X，算法终止。这种思路很显然是满足的限制要求的；第二种思路是我自己

想出的一个算法，这个算法也很简单，但是其正确性不是很好证明。

思路1：

CheckSum( A[1…n] , X )
1    MergeSort( A ) //从小到大排序
2    for i = 1 to n
3        if BinarySearch( A[1…n] , X-A[i] ) != –1 //假设BinarySearch在找不到指定元素的时候返回-1
4              return true
5    return false

思路2：

CheckSum( A[1…n] , X)
1    MergeSort( A ) //从小到大排序
2    i = 1
3    j = n
4    while( i < j)
5        if( A[i] + A[j] == X)
6             return true
7        else if( A[i] + A[j] > X)
8             j--
9        else if( A[i] + A[j] < X)
10           i++
11   return false

算法正确性证明：

思路1的正确性是显而易见的；思路2的正确性就不那么直观，其可能令人感到困惑的地方在于：思路2会不会漏掉某些情况？下面开始思路2的证明，

但是因为我也是初学，证明过程不是很严谨和规范。

首先，假设S中“不”包含两个和为X的元素，那么思路2的第5行的测试条件永远不会成真，那么最终算法一定会返回false。因此，证明思路2的正确性

便转化成证明：

若S中存在两个元素a和b，使得a+b==X，那么算法一定会返回true。（*）

为了证明（*）成立，下面首先证明思路2的算法在执行过程中满足如下的特性：

若S中存在两个元素a和b，使得a+b==X（不妨设a<=b），则在思路2的算法执行过程汇中，每一次迭代开始之前（即算法第4行执行之前），A[i…j]都包含a和b。（#）

下面采用归纳法证明（#）的成立：（令 i_k，j_k分别表示第 k 轮迭代开始之前 i 和 j 的取值，A[i_k…j_k]表示第k轮迭代开始之前的A[i…j]）

证明：
1、第 1 轮迭代开始之前，i₁=1，j₁=n。A[i_k…j_k]即为A[1…n]，a和b很显然包含在A[1…n]中，结论成立。
2、若第 k 轮迭代开始之前，A[i_k…j_k]包含a和b。则按照算法的执行步骤：
     （1）如果A[i_k]+A[j_k]==X，算法返回true，算法终止。
     （2）如果A[i_k]+A[j_k] > X，算法使得j_k值减1，即第 k+1 轮迭代开始之前，i_k+1 = i_k，j_k+1 = j_k- 1。下面证
             明A[j_k]不可能是a或者b中的任何一个：
             （2.1）因为a<b，且A[i_k…j_k]包含a和b，所以A[j_k]不可能是a。
             （2.2）假设A[j_k]等于b，因为A[]是从小到大排序的，所以，必然有：
                        A[j_k]+A[j_k-1] > A[j_k]+A[j_k-2] > A[j_k]+A[j_k-3] > … > A[j_k]+A[i_k+1] >A[j_k]+A[i_k] > X，即：
                        b+A[j_k-1] > b+A[j_k-2] > b+A[j_k-3] > … > b+A[i_k+1] >b+A[i_k] > X
                        也就是说a不可能是A[i_k…j_k-1]中的任何一个元素，这和前提：A[i_k…j_k]包含a和b 矛盾，所以假
                        设错误，所以A[j_k]不是b。
              因为A[i_k…j_k]中包含a和b，而又已经证明A[j_k]不是a或者b，又i_k+1 = i_k，j_k+1 = j_k- 1 ，所以，在第k+
              1轮迭代开始之前，A[i_k+1…j_k+1]一定包含a和b。
     （3）如果A[i_k]+A[j_k] < X，同理可证第k+1轮迭代开始之前A[i_k+1,j_k+1]一定包含a和b。
3、由1、和2、可知，每一次迭代开始之前，A[i…j]都包含a和b。

现在（#）已经得到证明，而由（#）证（*）是很直观的。因为A[i…j]中始终包含a和b，并且每一次迭代A[i…j]的规模小一，所以，最坏的情况是迭代一直执行到i+1=j的

时候，因为此时A[i,j]包含a和b，所以A[i]一定是a，A[j]一定是b，算法检测到A[i]+A[j] = a+b=X，算法返回true。

总结：以上便是全部内容，从理论上讲思路2应该要比思路1要快（虽然它们都是）。但是很明显地，思路1的正确性更加直观。