请教：用最少的比较次数求一个数组第二最小值

fsilence

给定数组A，怎样能用最少的比较次数能解决寻找第二最小值，并给出最坏情况下所用的比较次数，注意，这里不是问算法的时间复杂性，问的也不是数量级，而是具体的最坏强况下最小比较次数

[ 本帖最后由 fsilence 于 2006-2-17 20:31 编辑 ]

flw

好久没有写 C code 了。
试试看：

1. 因为楼主在要作业，所以我屏蔽掉了

复制代码

[ 本帖最后由 flw 于 2006-2-17 21:11 编辑 ]

ArXoR

给个大概的算法描述吧
把数组两两分组,如果数组大小为奇数,最后一个另外考虑
设 b为最大,a为次大
每次扫描到  (A_i,A_(i+1))
比较A_i和A_(i+1),设其中大的为y,小的为x,

如果y>b,则次大应为x和b里大的
如果y<=b,则次大应为y和a里大的

这样每对(A_i,A_(i+1))最多要3次比较

而如果剩下一个A_i,最多比较2次

所以最坏情况时数组大小为偶数,比较次数为3*n/2

PS:楼上兄弟的要2*n次吧...

ArXoR

汗...上面的算法改最大成最小就行了...
最近老是看错...

flw

原帖由 ArXoR 于 2006-2-17 21:07 发表
汗...上面的算法改最大成最小就行了...
最近老是看错...

不是你看错了，
是楼主改帖子了。由此可见，这个问题是个作业题，他发错了，又不会举一反三，因此重新改了，希望大家能给他一个准确的答案。
有鉴于此，我把我的帖子也编辑掉吧。

emacsnw

原帖由 fsilence 于 2006-2-17 04:22 发表
给定数组A，怎样能用最少的比较次数能解决寻找第二最小值，并给出最坏情况下所用的比较次数，注意，这里不是问算法的时间复杂性，问的也不是数量级，而是具体的最坏强况下最小比较次数

答案是 n + ceil(log n) -2
ceil 是上取整，log以2为底，至于为什么，楼主自己悟吧。。

ideawu

这个怎么样？

1. 
   
2. 
   
3. #include <stdio.h>
   
4. #include <time.h>
   
5. 
   
6. int main(){
   
7.         int a[10];
   
8.         int i;
   
9.         //init a[10]
   
10.         int max,smax;
    
11.         srand(time(0));
    
12.         for(i=0;i<10;i++){
    
13.                 a[i] = rand()%100;
    
14.                 printf("%d ",a[i]);
    
15.         }
    
16.         printf("\n");
    
17.        
    
18. 
    
19.         max = a[0];
    
20.         if(a[0] < a[1]) smax = a[1];
    
21.         else smax = a[0];
    
22.         for(i = 0;i<10;i++){
    
23.                 if(a[i] < max){
    
24.                         smax = max;
    
25.                         max = a[i];
    
26.                 }
    
27.                 else if(a[i] < smax) smax = a[i];
    
28.         }
    
29.         printf("max=%d; smax=%d;\n",max,smax);
    
30.         return 1;
    
31. }
    

复制代码

[ 本帖最后由 ideawu 于 2006-2-18 09:52 编辑 ]

emacsnw

原帖由 emacsnw 于 2006-2-17 15:59 发表


答案是 n + ceil(log n) -2
ceil 是上取整，log以2为底，至于为什么，楼主自己悟吧。。

厚道点，还是说吧。。其实方法很简单：
对n个数两两比较，即a[0] vs a[1], a[2] vs a[3],... 最后还有多的就轮空，每次比较的较小值“获胜”进入下一轮；
对最多ceil(n/2)个“获胜”者继续上述两两比较，知道最后决出“冠军”，这就是n个数的最小值。
我想很容易得知，这样得到最小值共进行了 n-1 次比较操作。

关键是：第二小的数一定是所有与最小值进行过比较的那些数中间的最小值。由于最小值一共进行了 ceil(log n)次比较，因此我们有 ceil(log n)个candidates. 从这么多数里找最小值需要的比较次数当然是 ceil(log n)-1。

总共需要的比较次数因此是 n + ceil(log n) - 2

yzc2002

原帖由 emacsnw 于 2006-2-18 10:25 发表


厚道点，还是说吧。。其实方法很简单：
对n个数两两比较，即a[0] vs a[1], a[2] vs a[3],... 最后还有多的就轮空，每次比较的较小值“获胜”进入下一轮；
对最多ceil(n/2)个“获胜”者继续上述两两比较，知 ...

这个是不是需要有O(n)额外空间的支持?不然如何记录中间结果呢?
ArXoR的方法是可行的

emacsnw

原帖由 yzc2002 于 2006-2-17 19:17 发表

这个是不是需要有O(n)额外空间的支持?不然如何记录中间结果呢?
ArXoR的方法是可行的

ArXoR的方法是可行的，但是题目好像只要求最少的比较次数，没说不能使用额外空间。
毕竟 n + log(n) 要比 1.5n 小很多。