首页 > 搜索 > 中位数的最大值和最小值算法,中位数 最大值 最小值

中位数的最大值和最小值算法,中位数 最大值 最小值

互联网 2020-10-24 07:47:29
在线算命,八字测算命理

n个数中同时找出最大值跟最小值:

例子:n = 7  

5  1  2  3  6  4  8

方法一:独立地找出最大值和最小值,各用n-1次比较,共有2n-2次比较。

方法二:成对地处理元素,先将一对输入元素相互比较,然后把较小者与当前最小值比较,把较大者与当前最大值比较,因此每两个元素需要比较3次。(n为奇数时,将最大值和最小值都设为第一个元素的值,然后成对地处理余下的元素,总共做了3*[n/2]次比较,[]为下界。n为偶数时,就对前两个元素做一次比较,以决定最大值和最小值的初始值,然后成对地处理余下的元素,总共做了3*(n-2)/2 + 2 = 3*n/2-2次比较,不管是哪一种情况,总的比较次数至多是3[n/2],[]为下界)

/* ---------------------------------------------------------------------------------------------------------------------------------*/

证明:在最坏情况下,利用n + [lg[n]] - 2 次比较,即可找到n个元素中的第二小元素。(提示:同时找最小元素)

常规查找:先找出最小值,用了n-1次比较,再找次小值,用了n-2次比较。一共用了2n-3次比较,无法满足题目要求。

我们可以利用树的结构来完成查找:成对比较,不断取小的值,这样可以求出最小值。而在比较的过程可以生成一棵树。具体如图

例子:n = 7  

5  1  2  3  6  4  8

        找出最小值(即根节点)需要比较的次数为n-1(其实是非叶子节点的个数),然后从根节点往叶子沿着某条路径开始寻找次小值(某条路径是指孩子节点的值 = 当前节点的值 的那条路径)。因为在生成树的时候次小值一定会跟最小值比较过,所以在沿着路径走的过程中,需要比较的元素是 孩子节点值 != 根节点值 的那个节点的值,即图中红色标记的结点,个数最多为lg(n)-1个,即树的高度 - 1(减去的是根节点,不需要比较)。找出红色结点的最小值即为最终的次小值。所以总的次数达到n + [lg(n)] - 2次。

遗憾的是~

经过测试,普通查找(比较次数 = 2n-3)比利用二叉树查找(比较次数 = n + [lg(n)] - 2)快上10多倍,可能是后者操作复杂引起的时间消耗。不过后者确实是个很好的思路!

贴上代码:

/* 产生测试数据 */#include #include #include #include int main(){freopen("in.txt", "w", stdout);srand(unsigned(time(NULL)));int n = 8000000;int i;printf("%d\n", n);for(i = 0; i < n; i++){printf("%d\n", rand()%n + 10);}return 0;}/* 包括最坏情况以 n + lg(n) - 2 的比较次数寻找数组中的次小值*//* 运行环境:windows平台 */#include #include #include #include #define N 100010000#define INF (1lchild = T->rchild = NULL;t[i] = T;}return 1;}void ShowInit(Tree *t[], int n){int i;for(i = 0; i < n; i++)printf("%d ", t[i]->data);printf("\n");}bool CreateTree(Tree *t[], int n){int len = n;int u, i;Tree *T;while(len > 1){u = 0;for(i = 0; i + 1 < len; i += 2){if(!Create(T)) return 0;T->data = MIN(t[i]->data, t[i+1]->data);T->lchild = t[i];T->rchild = t[i+1];t[u++] = T;}if(len & 1) t[u++] = t[len-1];len = u;}return 1;}void ShowTree(Tree *T){if(NULL == T) return;printf("%d ", T->data);ShowTree(T->lchild);ShowTree(T->rchild);}void FindSecMin(Tree *T, const int base, int &ans){if(NULL == T->lchild && NULL == T->rchild) return;if(base == T->lchild->data){ans = MIN(ans, T->rchild->data);FindSecMin(T->lchild, base, ans);}else{ans = MIN(ans, T->lchild->data);FindSecMin(T->rchild, base, ans);}}int main(){freopen("in.txt", "r", stdin);int i;Tree *T;int n, min2;while(~scanf("%d", &n)){#if 0for(i = 0; i < n; i++)scanf("%d", &a[i]);int flag = 0;int min1 = INF;/* --------------------------------------------------- */ FILETIME beg,end;//里的计时器GetSystemTimeAsFileTime(&beg);/* --------------------------------------------------- */for(i = 0; i < n; i++){if(a[i] < min1){min1 = a[i];flag = i;}}min2 = INF;for(i = 0; i < n; i++){if(a[i] < min2 && i != flag)min2 = a[i];}/* --------------------------------------------------- */GetSystemTimeAsFileTime(&end);long time = 100*(end.dwLowDateTime-beg.dwLowDateTime);/* --------------------------------------------------- */printf("%d\n", time);if(INF == min2) printf("Error!\n"); //只有一个数据else printf("min2 = %d\n", min2);#endif#if 1if(!Init(t, n)) return 1;//ShowInit(t, n); //显示初始数据/* --------------------------------------------------- */FILETIME beg,end;//里的计时器GetSystemTimeAsFileTime(&beg);/* --------------------------------------------------- */CreateTree(t, n); //创建树min2 = INF;FindSecMin(t[0], t[0]->data, min2); //寻找第二小的数值/* --------------------------------------------------- */GetSystemTimeAsFileTime(&end);long time = 100*(end.dwLowDateTime-beg.dwLowDateTime);/* --------------------------------------------------- */printf("%d\n", time);if(INF == min2) printf("Error!\n"); //只有一个数据else printf("min2 = %d\n", min2);#endif}return 0;}
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多