算法导论习题解答 2.3-7

amazingidiot

•2.3-7 请给出一个运行为Θ(nlgn)的算法（伪码），使之能在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。
解：解题思路：先对集合S进行归并排序，然后新建一个数组S1，使得S1 = x – S，再将两个数组并起来。如果在并的过程中发现有两个元素相等且两个元素一个来自S，一个来自S1，则可以确定S中存在有两个其和等于x的元素。
Find whether x exits
1、Sort(S)
2、for i <- 0 to Length(S) – 1
3、     do S1 <- x - S
4、for i <- 0 to Length(S) – 1
5、     do Merge( S,S1 ) 
6、        if S[p] > S1[q]
7、            S0[k] <- S[p]  p++ k++
8、        if S[p] < S1[q]
9、            S0[k] <- S[q]  q++ k++
10、       if S[p] == S1[q]
11、          return true
12、return false        
在第一行进行排序时，时间代价为Θ(nlgn)，后来的合并过程时间代价为Θ(n)，总的时间代价为Θ(nlgn)。