同時(shí)找出最大值和最小值的一種優(yōu)化算法-MaxAndMin
在一個(gè)有n個(gè)元素的集合中，單獨(dú)求出最大值（或最小值）的算法，很容易實(shí)現(xiàn)，只需按序掃描整個(gè)序列，記錄最大值（或最小值），其上限為n-1次。
但在很多應(yīng)用中，需同時(shí)找到最大值和最小值，一般情況大家較容易想到用上面的算法獨(dú)立的找到最大值和最小值，各用n-1次，共有2n-2次比較。這在大容量數(shù)據(jù)庫中（n很大），效率不是很高。
在這里，我將給出一種新的算法代碼，以大幅提高其效率（n很大時(shí)）。具體做法是：每次成對的處理數(shù)據(jù)，先將一對元素進(jìn)行比較，然后把較大者與當(dāng)前最大值比較，較小者與當(dāng)前最小者比較，因此每兩個(gè)元素需要3次比較。具體實(shí)現(xiàn)時(shí)需考慮n的奇偶，n為奇數(shù)，3【n/2】次；n為偶數(shù)，3n/2-2次。因此總的比較次數(shù)至多為3【n-2】。（注：【n】表示不大于n的整數(shù)）。
具體C++源代碼如下：
#include <iostream.h>
#include <limits.h> //包含INT_MAX，INT_MIN的頭文件
int nMax = INT_MIN; //將INT_MIN設(shè)為當(dāng)前最大值的初始值
int nMin = INT_MAX;
/**//////記錄比較最大值函數(shù)int Max(int nNum)
{
if (nMax<nNum)
{
nMax = nNum;
}
return nMax;
}
/**//////記錄比較最小值函數(shù)int Min(int nNum)
{
if (nMin>nNum)
{
nMin = nNum;
}
return nMin;
}
void main()
{
//測試序列
int nData[] = {3,2,5,9,4,2,1,13,0,-1,1380};
int nLen = sizeof(nData)/sizeof(nData[0]);
if (nLen%2 == 1) //待測數(shù)據(jù)為奇數(shù)
{
//待測數(shù)據(jù)為奇數(shù)，最值初始值均設(shè)為nData[0]
Max(nData[0]);
Min(nData[0]);
for (int i=1;i<=(nLen-1)/2;i++)
{
if (nData[i]>nData[nLen-i])
{
Max(nData[i]);
Min(nData[nLen-i]);
}
else
{
Max(nData[nLen-i]);
Min(nData[i]);
}
}
}
else //待測序列為偶數(shù)
{
for (int i=0;i<nLen/2;i++)
{
if (nData[i]>nData[nLen-i-1])
{
Max(nData[i]);
Min(nData[nLen-i-1]);
}
else
{
Max(nData[nLen-i-1]);
Min(nData[i]);
}
}
}
cout<<"nMax = "<<nMax<<endl<<"nMin = "<<nMin<<endl;
}posted on 2012-05-14 12:39
代碼之美 閱讀(6548)
評論(2) 編輯 收藏 引用