同时寻找最大数和最小数的最优算法 第二大数

时间:2021-03-05 00:44:41

我们知道,在一个容量为n的数据集合中寻找一个最大数,不管用什么样的比较算法,至少要比较n-1次,就算是用竞标赛排序也得比较n-1次,否则你找到的就不能保证是最大的数。那么,在一个容量为n的数据集合中同时寻找最大数和最小数的最小比较次数是多少呢?
     从一个容量为n的数据集合中同时找到最大数和最小数的最优方法是:首先让所有的元素参与两两比较,这样总共比较了n/2次,最大数肯定在胜者组中,最小数肯定在败者组中;然后从容量为n/2的胜者组中找到最大的数,最少要比较n/2 - 1次;同理,从容量为n/2的败者组中找到最小的数,最少要比较n/2 - 1次。所以总共需要比较 (3n/2) - 2次。以上假设n为偶数。奇数同理。

这是同时寻找最大数和最小数的最优算法

 

    那么,我们要从一个容量为n的数据集(假设该数据集是一个集合,即没有相同的元素)中找到第二大元素需要多少次比较呢?
    一种习惯的方法是:先找出最大的元素,这需要比较n-1次;然后从剩下的n-1个元素中找到最大的,这个元素就是我们要找的第二大元素,这需要比较n-2次。做一总共比较2n-3次。
但是,
    还有一个更优的方法:
(1) 我们考虑淘汰赛的比较法,淘汰赛结束后,找出冠军我们需要n-1次比较;如下图所示,找到12需要比较7次。
(2) 此时我们要考虑到,亚军应该存在于败给冠军的这些选手中(否则,每个元素都至少有两个元素比它大),由于与冠军比过的元素个数为┌log2n┐,从这些元素中找到最大值需要比较┌log2n┐ - 1次;如下图所示,亚军应该在10,11,4这三个元素中。否则,如果亚军是5,那么冠军12比它大,与它比较过的10也比它大,至少两个元素大于5,所以5肯定不是亚军的候选者。

 

同时寻找最大数和最小数的最优算法 第二大数


(3)从而找出亚军要比较n-1+┌log2n┐-1 = n-2+┌log2n次比较。这个算法是寻找亚军的最优算法





分治与递归——最大值和次大值的最优算法


问题描述:输入n个数,最坏情况下用 n + logn - 2 次比较找出当中的最大值和次大值。

算法思想:根据题意出现logn,则肯定用到二分或者堆的思路,但是输入的数没有经过排序,而且题目要求的计算量也不允许排序。这样,就肯定会用到类似堆的思路,但是直接构造堆等同于排序。堆的思想跟竞标赛类似,都是父节点>=<=)子节点。如果父节点都是从子节点而来,这样就是竞标赛;如果不是,这样就是堆。既然不能排序又不能构造堆,那就只能用竞标赛的思想,通过二分来进行最多logn次竞赛,选出最大值(冠军),而次大值(亚军)只能在与最大值的比较中被淘汰(亚军的实力只可能输给冠军),故在所有被最大值(冠军)淘汰的数值中选取次大值,最多也是logn次比较,满足题意(由于题意只限制了比较次数,故实现过程并没有考虑时间复杂度和空间复杂度)

代码实现:

//最大值和次大值的最优算法,数组中可能存在重复元素,不能处理最大值是0的情况

#include <stdio.h>

#define N 1000

int m[2*N];

int num[2*N];

int biaoji[N];

int bigger(int i)

{

    if(num[i]>num[i+1])

    {

        biaoji[m[i+1]]=num[i];

        return i;

    }

    else

    {

        biaoji[m[i]]=num[i+1];

        return i+1;

    }

}

int work(int a,int b)

{

    int i,j;

    while(a<b)

    {

        for(i=a;i<b;i+=2)

        {

            j=bigger(i);

            num[i/2]=num[j];

            m[i/2]=m[j];

        }

        if(i==b)

        {

            num[i/2]=num[i];

            m[i/2]=m[i];

        }

        a=a/2;

        b=b/2;

    }

    return num[a];

}

int work2(int l,int max)

{

    int i,flag=1;

    int bmax;

    for(i=l;i<2*l;++i)

    {

        if(biaoji[i-l]==max)

        {

            if(flag)

            {

                flag=0;

                bmax=num[i];

            }

            else if(bmax<num[i])

                bmax=num[i];

        }

    }

    return bmax;

}

int main()

{

    int i,l;

    int max,bmax;

    int f,start;

    while(true)

    {

        printf("please putin the length:\n");

        scanf("%d",&l);

        if(l==0)

            break;

        printf("please putin num[]:\n");

        for(i=l;i<2*l;++i)

            scanf("%d",&num[i]);

        for(i=l;i<2*l;++i)

            m[i]=(i-l);

        max=work(l,2*l-1);

        bmax=work2(l,max);

        printf("the max is %d and the bmax is %d\n",max,bmax);

    }

 

    return 0;

}