同時找出最大值和最小值的一種優化算法-MaxAndMin
在一個有n個元素的集合中，單獨求出最大值（或最小值）的算法，很容易實現，只需按序掃描整個序列，記錄最大值（或最小值），其上限為n-1次。
但在很多應用中，需同時找到最大值和最小值，一般情況大家較容易想到用上面的算法獨立的找到最大值和最小值，各用n-1次，共有2n-2次比較。這在大容量數據庫中（n很大），效率不是很高。
在這里，我將給出一種新的算法代碼，以大幅提高其效率（n很大時）。具體做法是：每次成對的處理數據，先將一對元素進行比較，然后把較大者與當前最大值比較，較小者與當前最小者比較，因此每兩個元素需要3次比較。具體實現時需考慮n的奇偶，n為奇數，3【n/2】次；n為偶數，3n/2-2次。因此總的比較次數至多為3【n-2】。（注：【n】表示不大于n的整數）。
具體C++源代碼如下：
#include <iostream.h>
#include <limits.h> //包含INT_MAX，INT_MIN的頭文件
int nMax = INT_MIN; //將INT_MIN設為當前最大值的初始值
int nMin = INT_MAX;
/**//////記錄比較最大值函數int Max(int nNum)
{
if (nMax<nNum)
{
nMax = nNum;
}
return nMax;
}
/**//////記錄比較最小值函數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) //待測數據為奇數
{
//待測數據為奇數，最值初始值均設為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 //待測序列為偶數
{
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
代碼之美 閱讀(6534)
評論(2) 編輯 收藏 引用