算法导论2.3-7习题解答(合并排序算法及二分查找)
CLRS 2.3-7 :请给出一个运行时间为O(nlgn)的算法,是之能在一个由n个整数构成的集合S和另一个整数x时,判断出S中是否存在有两个其和等于x的元素。 算法思想:1.先运用合并排序进行排序 O(nlgn),2.然后运用二分查找法寻找y,y = x - a[i]; 代码如下: 1 #i...
算法导论2.3-7
方法1、 先排序,然后比较: 1 int i=0, j=n-1; 2 int b=0; 3 while (i<j) 4 { 5 int k=s[i]+s[j]; 6 if (k==x) b=1,break; 7 else if (k<x) i...
算法导论之2.3-7练习题
题目:给出一个Θ(nlgn)时间的算法。判断在集合S中,是否存在两个元素的和为x。 算法导论的教师手册解法如下:1.对集合S排序。 2.创建集合T = {z : z = x − y ,y ∈ S}。 3.对集合T排序。 4.去除S和T中的重复元素。 5.按照从小到大顺序或者从大到小顺...
从头看算法导论 习题2.3-7 深入分析
题目:请给出一个时间复杂度为nlogn的算法,使之能够在给定一个由n个整数的构成的整合S和另一个整数x时,判断出S中是否存在有两个其和等于x的元素。 算法思想:1.先运用合并排序进行排序 O(nlgn),2.然后运用二分查找法寻找y,y = x - a[i],算法的时间复杂度小于nlogn,所以总的...
算法导论2.3-7习题
先使用归并排序进行排序,再建立其补集,对这两个排序后的集合进行元素比较,找到相同元素即寻找到答案 def findthecomplementary(s, x): l1 = list(s) l2 = [] n = len(l1) mergesort(l1, 0, n-1) ...