这只是一道书本上的简单练习题.
这里列出了三种方法，其中方法一是最原始的方法O(n^2)，方法二是书上的标准答案O(nlgn)，方法三是我做题时用的方法O(n)。
原始题目如下：Given a set S of n integers and another integer x, determine whether or not there exist two elements in S whose sum is exactly x.
大概意思就是：给定含n元素的集合S和整数x,判断集合S中是否有两个数的和恰好等于x.
稍微精确一点就是：设有集合S{a1,a2,…,an}和整数x,试问能否在S中找到ai和aj( 0<i<j<n+1 ),使得 ai + aj = x ?
方法一:
用最原始的两层循环搜索办法,worst case时间复杂度为O(n^2)
方法二:
O(n)+O(n)+…+O(n)不会超过O(n)
O(nlgn)+O(nlgn)+O(nlgn)不会超过O(nlgn)
由于在n->∞的时候O(nlgn)的算法会比O(n^2)算法速度快,所以可以考虑采取”人海战术”,在S上顺序地多跑几次O(nlgn)的算法,能否解决问题?
设有ai、aj( 1<= i!= j <=n ) ∈S , 且ai + aj = x ,则 aj = x – ai, 已知ai以后,如果能在S中找到一个数值等于x - ai,则成功.
现在假设S中没有重复的数字.
Step1. 对S进行排序. Worst case O(nlgn)时间内可以完成.
Step2. 开辟一个辅助数组V={b1,b2,…,bn},使得bi=x – ai (1 <= i <= n). O(n)时间内搞定.
Step3. 对V进行排序.同样O(nlgn).
下面问题变了:在V中能不能找出一个bj,使得在S中能找出与之对应的ai,且有bj = ai?
Step4. S和V已经排序.共2n个元素,现在开辟一个2n空间的数组E,将S与V有序的合并到E.
Step5. 在E中去找有没有连续两个相同的元素ai,ai+1,若找到,则S中有两个元素和为x.
算法的总体复杂度 = O(nlgn) + O(n) + O(nlgn) + O(n) + O(n)
= O(nlgn)
所以在理论上,或在大规模的数据查找中,方法二是优于方法一的.假设有nk,使得当n>nk时,方法二优于方法一.对于方法二来讲,这个nk值会很大.
方法一是蠢方法,不过大家都知道, maintainability高, robustness高;
方法二是标准答案,在大规模数据查找的时候能显示出优势.不过既然是大规模数据处理,算法执行时又多new了2n的buffer,如果heap overflow的时候new failed,算法是准备直接返回一个”本问题算法拒绝执行”呢还是怎么办?
本人做这个练习的时候用的是下面的方法三,robustness比2更差,不过在小规模小数据集的时候,是能比一的效率高不少.
我的方法三:
相比传统的方法一,主要想实现目标有两个:
一是尽量把线性查找换成别的复杂度更低的查找.这里我用了直接映射。
二是利用一些辅助空间记录一些搜索过程中已知的信息，这里我用了辅助向量。
假设现在有整数集合S={a1,a2,…,an}和整数x.现在假设算法所应用的范围中,可能出现的最大的整数是NMax,最小整数是NMin. 设m = NMax – NMin + 1
现在开辟一个新的数组V={b1,b2,…,bm}.这样,算法应用范围中的所有数字k都可以映射到V上去: V[ k - NMin ].
下面是算法:
Step1: 将V数组清0.
Step2: 对S中的每个元素ai(0<i<n+1),
如果V[i]为零,则V[i] = 1;
如果V[x-i]为零,则V[i] = 1;
否则退出,找到ai+aj=x;
Step3: 如果step2的循环能顺利执行到最后,则没有符合条件的ai和aj,使得ai+aj=x.
本算法可以作下面的扩展:如果要求找出S中符合条件的ai和aj,或者要求找出S中所有符合条件的ai和aj,则可以改进一下,在step2中不判断,就做两件事:
V[i] = V[i] + 1
V[x-i] = V[x-i] + 1
循环一遍后再顺序搜索一遍即可.
算法的时间复杂度嘛: Step1要O(n)
Step2要O(n)
Worst Case算法时间复杂度 = O%2
|