算法入门---判断集合S中是否存在两个其和等于x的元素

 

此题是算法导论（第二版）第二章习题 2.3-7，题目如下：

请给出一个运行时间为O（n lgn）的算法，使之在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。

思路一 ：我们最容易想到的是O（n²）的算法，大致伪码即：

1 findX(A, x){

2     for i=0 to length[A] {

3         key = A[i]

4             for j=0 to length[A]{

5                  if(j != i && key + A[j] == x ){return true}

6     }

7     return false

8 }

这里的算法不符合O(n lgn)，所以不行。

思路二：改进思路一中的算法，使第一层循环里面的4--5行的效率为 lgn。

既然4-5行的目的是找到某个符合条件的值，那么我想到了二分查找，二分查找是一个最坏O(lgn)的查找算法，但是前提是集合S有序，于是先要进行排序。伪码如下：

1 findX(A, x){

2     mergeSort(A, 0, length[A]);

3     for i=0 to length[A] {

4         key = A[i]

6         if( binarySearch(A, x-key, 0, length[A]) != i ){return true}

7     }

8     return false

9 }

第2行的归并排序运行时间为O(n lgn), 第3-7行的运行时间为O(n)*O(lgn)= O(nlgn)，故总运行时间为O(nlgn)。

 

思路三：下面的算法来自算法导论的教师手册

1 将集合S排序

2 生成新的集合 S’ = {z: z = x-y} y∈S

3 将S’排序

4 使S或者S’中每个值只出现一次

5 将S和S'进行合并（Merge方法）

6 当且仅当合并后的输出序列中有相同元素，则S中存在两个元素其和等于x。

运行时间分析： 第1步和第3步均为O(n lgn)，第2,4,5,6步为O(n), 故总运行时间为O(nlgn)。