算法导论（第9章-中位数和顺序统计学）最大值和最小值
博客搬家：最爱午后红茶
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 (1<<30)
#define MIN(x, y) ((x) < (y) ? (x) : (y))typedef struct TREE
{int data;TREE *lchild, *rchild;
}Tree;Tree *t[N];
int a[N];bool Create(Tree *&T)
{T = NULL;T = (Tree *)malloc(sizeof(Tree));if(NULL == T){printf("Error! overflow!\n");return 0;}return 1;
}bool Init(Tree *t[], int n)
{int i;Tree *T;for(i = 0; i < n; i++){if(!Create(T)) return 0;scanf("%d", &T->data);T->lchild = 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;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！