2011-03-11算法导论第9章

    技术2022-05-13  14

     

    好几天前看完的这一章可是一直没写,因为没写,总感觉印象不是很深刻,幸好,现在有点时间,巩固一下。

    这一章总共涉及到3个算法,第一个算法很有趣,它的问题是: 一个数组datan个元素,怎么同时找出最大值和最小值?最直接的算法无疑是下面的:

    int max = min = data[0]; for(int i=1; i<data.length; i++) { if(max<data[i]) { max = data[i]; }; if(min>data[i]) { min = data[i]; }; } 

    可是这样的话,总共比较了2n-1)次,有没有更好的算法呢?当然有,下面看看这个更好算法。

    这个算法的思想是,先给minmax初始化,然后将数组中的元素一对一对的进行比较,比较出来的较大的值再与max比较,较小的值与min进行比较,并作相应的处理(如,给maxmin赋新的值等等)。这样下来,第一对值比较了3次,总共比较了3*(n/2)次。这看起来不像从O(n^2)降到O(nlgn)那么明显,不过这的确是一个有趣的算法。

    代码:

    //同时取得最大值和最小值,int[0]是最小值,int[1]是最大值 public int[] getMaxAndMin() { //先处理一些数组长度方面的特殊情况 int len = data.length; if(len==0) { System.out.println("数组中无数据"); return null; } else if(len==1) { min = max = data[0]; } //对min,max进行初始化,根据数组长度奇偶性不同的,有不同的初始化方法 boolean odd; //用来标志数组长度的奇偶性,在下面代码中还要用到 if(len%2==1) { //如果是长度为奇数,则min和max都初始化为第一个元素 min = data[0]; max = data[1]; odd = true; } else { //如果是长度为偶数,则min初始化为第一、二个元素中较小的数,max初始化为较大的数 if(data[0]<=data[1]) { min = data[0]; max = data[1]; } else { max = data[0]; min = data[1]; } odd = false; } //将数组中剩下的元素一对一对进行比较,将比较的结果保存在bigger, smaller中 //再将bigger, smaller分别和max、min进行比较,并做相应的处理 int bigger, smaller; int i = odd?1:2; for(; i<len; i++) { if(data[i]<=data[i+1]) { smaller = data[i]; bigger = data[i+1]; } else { smaller = data[i+1]; bigger = data[i]; } min = (smaller<min)?smaller:min; max = (bigger>max)?bigger:max; i++; //每次i步进2,所以在这里还要进行一次i++ } int[] result = new int[2]; result[0] = min; result[1] = max; return result; } 

    第二个算法讲的是从数组data中找出第i小的值(MINi表示吧)。这个问题看似也好办,先将数组进行排序嘛,然后MINi不就一下就出来了?然而,先进行排序的话,用最popular的快排,所需时间是O(nlogn),算法的一个很重要的作用就是在解决问题的前提下,怎么样提高效率?

    对于当前的这个问题,书上提出一种平均时间在O(n)内找出MINi的算法,这个算法有点像二分法查找,先用快速排序中的partition算法,将数组分成2部分,再将ipivot的下标(用Ip表示吧)进行比较,如果i==Ip,那么不用说pivot就是所求的值,这点稍微思考一下,应该很快能理解的。如果iIp的话,则说明MINi应该处在partition所划分的前半部分,接下来对前半部分进行递归处理。类似的,如果i>Ip的话,则说明MINi应该处在后半部分,接下来对后半部分进行递归处理。直到某一次递归处理中,i==Ip,这样,便找出了MINi

    代码如下:

    //返回startend之间第i小的元素值

    public int randomizedSelect(int start, int end, int i) { System.out.println("start: "+start+" end: "+end+" i: "+i); if(start==end) { return data[start]; } int m = randomizedPartition(data, start, end); int k = m - start + 1; //k的值是从start开始,data[m]的位置 if(i==k) { return data[m]; } else if(i<k) { return randomizedSelect(start, m-1, i); } else { return randomizedSelect(m+1, end, i-k); } } 

    其中涉及到的randomizedSelect与前面所讲的快排中的randomizedSelect是一样的。

    第三个算法就比较复杂了,但是它解决的问题与第二个是一样的,前面也提到过,第二个算法是在平均条件下,时间复杂度是O(n),那么第三个算法就更进一步,在最坏的条件下,时间复杂度依然是O(n)。我们叫这个算法为SELECT,它的思想大概是这样的:

    1.首先,将这n个数分成ceiln/5)组,每组5个元素,最后一组n%5个元素。

    2.Insertion Sort将每组进行排序,找出它们的中位数,总共有ceiln/5)个。

    3.用递归的调用SELECT,在第二步找出的ceiln/5)个中位数,找出他们的中位数(中位数中的中位数),用x表示。

    4.x作为pivot对数组中的n个元素进行快速排序中的partition,如果m表示partition后小于x的部分中的元素个数,则说明x是数组中的第m+1小的元素。

    5.如果i==m+1,则x就是所要找的值。否则,如果im+1,则递归调用SELECT,在小于x的部分中找第i小的元素。如果im+1,则递归调用SELECT,在大于x的部分中找第i-(m+1)小的元素。

    如果熟悉快排,熟悉递归,则上面的算法还是比较容易理解的,但是我实现了一下,没有成功,原因未知,下次解决了,再把代码贴上来吧。

     


    最新回复(0)