算法导论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) ...