首页 > 代码库 > 从头看算法导论 习题2.3-7 深入分析
从头看算法导论 习题2.3-7 深入分析
题目：请给出一个时间复杂度为nlogn的算法，使之能够在给定一个由n个整数的构成的整合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。
算法思想：
1.先运用合并排序进行排序 O(nlgn)，
2.然后运用二分查找法寻找y，y = x - a[i]，算法的时间复杂度小于nlogn,所以总的时间复杂度还是nlogn。
批注：该思想，不是最好的（从简洁、时间复杂度上得到结论），不喜勿喷。
代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MAX 99999 4 #define MAXINT 0xFFFF-1 5 int num[MAX]; 6 7 void UniteSort(int *a,int start,int mid,int end) 8 { 9 int left_len=mid-start+1+1,right_len = end-mid+1;//加一个位置用于保存哨兵10 int *left = (int*)malloc(sizeof(int)*left_len);//加一个位置用于保存哨兵11 int *right = (int*)malloc(sizeof(int)*right_len);12 13 for(int i =0; i < left_len-1; i++)14 left[i] = a[start + i];15 left[left_len-1]=MAXINT;16 for(int i =0; i < right_len-1; i++)17 right[i] = a[mid + i +1];18 right[right_len-1]=MAXINT;19 20 int m=0,n=0; 21 for(int i=start;i<=end ;i++)22 {23 if(left[m]<=right[n])24 {25 a[i]=left[m];26 m++;27 }28 else29 {30 a[i]=right[n];31 n++;32 }33 }34 free(left);35 free(right);36 }37 38 void merge(int *a,int start,int end)39 {40 if(start<end)41 {42 int mid = (start+end)/2;43 merge(a,start,mid);44 merge(a,mid+1,end);45 UniteSort(a,start,mid,end);46 }47 }48 49 //二分查找50 bool binary_search(int* a, int n, int goal)51 {52 int middle = (n -1)/2;53 int high = n -1;54 int low =0;55 while(low <= high) {56 if(a[middle] == goal)57 return true;58 else if(a[middle] >= goal)59 high = middle -1;60 else61 low = middle +1;62 middle = (low + high)/2;63 }64 return false;65 }66 67 int main()68 {69 int x;70 scanf("%d",&x);71 // init72 for(int i=0;i<MAX;i++)73 num[i]=MAX-i;74 75 merge(num, 0, MAX -1);76 77 for(int i =0; i < MAX; i++)78 if(binary_search(num, MAX, x - num[i])) 79 {80 printf("YES\n");81 break;82 }83 84 return 0;85 }
刚才提到，还有更好的代码，这里不得不介绍拉。
首先归并算法，不是最好的？比归并排序还要好的是“快速排序”。可能有人要问为什么？（它们的时间复杂度，平均都是nlgn,快排最坏的情况是n的平方）分析如下：
快速排序算法和合并排序保持在相同的数量级下,但面对越大基数的无序数列时,快速排序的用时更短.——结论选自：快速排序与合并排序的分析与比较 （百度文库）
为什么造成这样的情况呢？因为快速排序是原地排序，归并是递归调用，没在原地操作（这里有人不要说，快排不稳定的废话了）。如上面的代码，归并排序中，临时开闭了新的数组空间而照成时间的流失（归并需要额外空间 ）——参考《深入理解计算机系统》局部性原理。
故，这里排序换成快速排序，在基数大的情况下，快速排序最快拉。
如上又提到“简洁”，在STL中，有现成的快速排序函数qsort、二分查找函数binary_search.我们得站在巨人的肩膀上····
在同样的条件下，sort()(默认从小到大排序)，也是不错的选择。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <algorithm> 4 5 #define MAX 99999 6 #define MAXINT 0xFFFF-1 7 int num[MAX]; 8 9 int comp(const void*a,const void*b){return*(int*)a-*(int*)b;}10 int main()11 {12 int x;13 scanf("%d",&x);14 // init15 for(int i=0;i<MAX;i++)16 num[i]=MAX-i; 17 18 // qsort(num,MAX,sizeof(int),comp);19 std::sort(num,num+MAX);20 for(int i =0; i < MAX; i++)21 //binary_search返回值: 如果数组中找到target, 返回其下标;否则返回 -122 if(std::binary_search(num, num+MAX, x - num[i])!=-1) 23 {24 printf("YES\n");25 break;26 }27 28 return 0;29 }
从头看算法导论 习题2.3-7 深入分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。