算法导论习题解答 2.3-7
•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 > S1
7、 S0 <- S p++ k++
8、 if S < S1
9、 S0 <- S q++ k++
10、 if S == S1
11、 return true
12、return false
在第一行进行排序时，时间代价为Θ(nlgn)，后来的合并过程时间代价为Θ(n)，总的时间代价为Θ(nlgn)。
页:
[1]