同时寻找最大数和最小数的最优算法 第二大数
我们知道,在一个容量为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个数,最坏情况下用?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) { ? ? ? ? ? ? ? ? } int work(int a,int b) ? ? ? ? ? ? ? ? ? ? ? ? ? ? int work2(int l,int max) ? ? ? ? ? ? ? ? ? ? int main() ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |