[算法Tutorial]Sort & Selection in O(n)

1. 寻找第k大（小）的数

假设数据存储在数组a[1..n]中

首先，寻找一个数组中最大或者最小的数，因为最大（小）的数一定要比其他所有的数大（小），因此至少要比较完所有的pair才能确定，所以时间复杂度在$O(n)$。那么寻找第k大（小）呢？

比较直观的，就是对数组中国所有的数据先进行排序，在我们这种渣渣的计算机入门选手而言，可选的有QuickSort，MergeSort和HeapSort，甚至是ShellSort等一些比较高级的方法啊...一般的代价都在$O(nlog n)$上，然后直接取出即可。

在算法导论的第九章，提出了一个效率更高的Selection算法，用到的主要原理就是分治，是根据QuickSort改编的，但是主要的不同的是，QuickSort会递归处理划分的两边，而这里的Selection则是只处理一半。因为要寻找第k小的数，那么如果k比之前的partition处理后，返回的位置下标要小，那么第k小的数一定在partition的pivot的左边一半，右边一半可以不用处理；若是k比这个pivot的下标要大，那么显然，要找的值在pivot的右边，但是这里有一点特殊，下一次递归查找的时候，是要寻找第（k-pivot下标）的数啦~

嗯，感觉好厉害的样子。然后让我来练练手。

 1     int partition(int[] a, int start, int end, int pivot) {//pivot为可以自己定义选定的参照值
 2         int i = start;
 3         int j = start;
 4         for(j = start; j < end; j++) {
 5             if(a[j]<=pivot) {                
 6                 int temp=a[i];
 7                 a[i]=a[j];
 8                 a[j]=temp;
 9                 i++;
10             }
11         }
12         int temp2 = a[i];
13         a[i]=a[end];
14         a[end]=temp2;
15         return i;        
16     }
17     
18     int selectkth(int[] a, int start, int end, int k) {
19         if(start == end) 
20             return a[start];
21         int q = partition(a,start,end,a[end]);
22         int p = q-start+1;
23         if(k == p)
24             return a[q];
25         else if(k < p) {
26             return selectkth(a, start, q-1, k);
27         }
28         else return selectkth(a, q+1 , end, k-p);        
29     }

2.前k大的数(算法导论思考题1)

其实，在我们老师上课的时候，比较强调selection和partition的“化学作用”啊，如果问题变为找出前k大的k个数呢？当然，万能的排序还是OK的啊，直接排序完输出就好了，简直66666...

后来，作业题中出现了一些比较厉害的东西啊，它可以达到$O(n + klog n)$啊，居然要用到建立一个堆啊，显然，算法导论上第六章说道，建立一个堆只需要线性时间啊，各种fix的操作也只需要logn啊，那不就是建个最大堆，然后提取k次root顺带着调整一下么...其实我喜欢说修理啊哈哈哈哈....

再后来，还有一个问题，说是可以到$O(n+klog k)$啊，你TM真是够了啊，然后，就是selection选出第k大的数啊，然后用这个数进行partition啊，把比他大的数用一次排序就好了啊，喂，你真是够了啊！

3. Selection + Partition共同解决一些问题

为了进一步blablablabla，老师真的是很强调这个Selection+Partition啊

Question 1：算法导论的第九章的思考题就有一个，叫做weighted-median。

显然啊，我觉得排序算法解决一切啊，有木有！！但你他喵的非得线性时间干嘛啊~

嘿嘿，然后来了啊，选出中位数啊，嘿嘿，然后进行partition，从头开始计算权重的和啊，看看跟1/2怎么样？小？OK，权重不够哦，再在右边一半进行Median的Selection+Partition啊，再进行计算吧，带上前面算出来的权重和啊，再去跟1/2比较...要是第一趟处理就比1/2大，那就在左边做一次中位数Selection+Partition吧...嘿嘿嘿嘿，大概估算一下，它的cost应该是在$n imes(1+1/2+1/4+1/8+...+1/(2^n))$吧...其实也就是$O(2n)$的样子，不错了吧，嘿嘿

Question 2：寻找最近接Median的k个数...（算法导论9.3-7题）

老规矩，排序啊，有木有！！！为什么又是线性时间呢？但是，老师这么说肯定是有用意的。好啦，我能想到的方法呢，就是先Select出中位数，cost=n，然后呢，就是对每个数与这个中位数做差取绝对值啊，然后这里的每个差的绝对值中，选出前k小的数，根据2中的原理，也就是$O(n+klog k)$的cost，然后映射回去原来的数，总体而言，的确是$O(n)$的cost吧（如果k不是特别大的话）。老师上课在讲Tutorial的时候，还提出了另一种差不多的方法，大致思路也就是selection+partition这个主题啦~~第一次选出中位数selection，记为M，加一次partition，共计$O(2n)$，两边各自寻找中位数，只保留接近中位数M的一半，直到差不多在第一次的中位数M左右两边各有k个数左右，然后选出差值最小的k个数...总之就是缩小范围，然后再集中处理的样子吧，时间大概是一个等比级数的求和$n imes(2+2/2+2/4+2/8+...+2/{2^k})$，还是在$O(n)$的级别的，但我总觉得绕了这么一大圈...哎，网上搜了一下，大多数都是直接一次上来就做差的啊...(莫非是我记错了？？

4. PK法

PK让我想起了年少无知的我看超女快男的经历啊。这里，我们老师主要用这种方法解决一些Selection相关的问题。

PK法的前提是我想要的超过总数的一半，主要思路是，每次都对等的淘汰两个或一个，若淘汰两个，至少有1个是我不想要的，若只淘汰了一个，那么我必定是我不想要的那个！这样淘汰直到最后，剩下的一定是我想要的。当然，若事先不知道前提是否成立，那么在得到结果以后，还要进行一次check！

Question 3：寻找出现频率最高的数，直接贴代码吧...

 1     int pk(int[] a) {
 2         int x = a[0];
 3         int count = 0;
 4         for(int i=0; i<a.length; i++) {
 5             if(a[i] == x) 
 6                 count++;
 7             else if(count >= 1)
 8                 count--;
 9             else {
10                 //start from begin
11                 count = 0;
12                 //why i+1? for next item is a[i+1], then count will ++
13                 //delete this pair of two
14                 x = a[i+1];
15             }
16         }
17         //check
18         int y = x;
19         count = 0;
20         for(int i = 0; i<a.length; i++) {
21             if(a[i]==y) {
22                 count++;
23             }
24         }
25         if(count>a.length/2)
26             return x;
27         else
28             return -1;
29     }

还有一个扩展问题：现在数组中没有出现频率一半的数字了，但有三个都超过了四分之一，找到他们。

有兴趣的可以去看看这儿：http://www.cnblogs.com/jy02414216/archive/2011/03/04/1970497.html

Question 4：VLSI芯片测试

　　　　Diogenes教授有$n$个被认为是完全相同的VLSI芯片，原则上它们是可以互相测试的。教授的测试装置一次可测二片，当该装置中放有两片芯片时，每一片就对另一片作测试并报告其好坏。一个好的芯片总是能够报告另一片的好坏，但一个坏的芯片的结果是不可靠的。这样，每次测试的四种可能结果如下：

　　　　A芯片报告　　　　　　　　　B芯片报告　　　　　结论

　　　　B是好的　　　　　　　　　　A是好的　　　　　　都是好的，或都是坏的

　　　　B是好的　　　　　　　　　　A是坏的　　　　　　至少一片是坏的

　　　　B是坏的　　　　　　　　　　A是好的　　　　　　至少一片是坏的

　　　　B是坏的　　　　　　　　　　A是坏的　　　　　　至少一片是坏的

a）证明若多于n/2的芯片是坏的，在这种成对测试方法下，使用任何策略都不能确定哪个芯片是好的。假设坏的芯片可以联合起来欺骗教授。

b）假设有多于n/2的芯片是好的，考虑从n片中找出一片好芯片的问题。证明n/2对测试就足以使问题的规模降至近原来的一半。

c）假设多于n/2片芯片是好的，证明好的芯片可用$Theta(n)$对测试找出。给出并解答表达式测试次数的递归式。

注：VLSI——Very Large Scale Integrated.

算法分析：

a)    在所有的策略中，时间复杂度最高但最有效的方法是：对每个芯片，让其它所有芯片对它进行报告，由于好芯片数目小于$n/2$，对于任意芯片，坏芯片都可以让判断结果一模一样（比如判断结果好坏各占一半），此时，就无法判断出好坏。得证。
b)    问题可以这么理解，证明：当多于$n/2$的芯片是好的时，可以通过【n/2的下界】次操作，得到一个包含至多$n/2$个芯片的集合，且该集合内好的芯片大于一半。这样，以后只需要在这个集合上执行类似的判断动作就好了。
对于n个芯片的集合，假设$good$代表好芯片的数目，则坏芯片有$(n – good)$个，将$n$个芯片两两组合，接下来分类讨论。
        1.    当n为偶数时，假设好芯片和坏芯片组成的对数为r，则$(n - good) geq r$。对每个对，如果结果是情况2、3、4，则不做任何操作，如果结果是情况1，则从中挑出一个放到一个集合中。所以，我们可以在好芯片对中取到$dfrac{good – r}{2}$个芯片，从坏芯片对中取到m个芯片，$m leq dfrac{n – good - r}{2}$。因为$dfrac{good – r}{2} > dfrac{n – good - r}{2}$，所以新集合中好芯片的数目大于一半，另外总芯片数小于等于$left(dfrac{n}{2} - r ight)$。
        2.    当n为奇数时，提取一个芯片，对剩下的芯片采取偶数的方法，只不过最后的集合情况是：$dfrac{good – r}{2} geq dfrac{n – 1 – good - r}{2}$，芯片总数小于等于$left(dfrac{n – 1}{2} - r ight)$。
                1)  当总数是偶数时，要么好的芯片数和坏的芯片数一样，原先被提取的芯片是好的芯片，把好的芯片加入集合；要么好的芯片比坏芯片多偶数个，此时不论被提取的芯片是好是坏，把它加入集合也能保证好的芯片数大于坏的芯片数。
                2)  当总数是奇数时，好的芯片数必然大于坏的芯片数。
       得证。
c)    当每次的r为0时，所需要的递归次数最多，$T(n) = T(n/2) + n/2$。

(请原谅我直接贴了别人的博客:http://www.cnblogs.com/longdouhzt/archive/2011/07/15/2107751.html内容...)

[算法Tutorial]Sort & Selection in O(n)

相关推荐