主题：求教一个问题
xinanfish
[专家分：10] 发布于 2006-04-06 22:19:00
在最坏情况下用[3n/2-2]次比较找出数组a[n]中的最大值和最小值
回复列表 （共3个回复）
沙发
rickone [专家分：15390] 发布于 2006-04-06 22:43:00
有难度，呵呵
板凳
lutree1985 [专家分：3490] 发布于 2006-04-07 22:36:00
这里只说算法
具体的楼主自己试试看吧
template<class Type>
void MAXMIN(Type L[],int n,Type M1,Type M2){
if(n==2)
{ if(L[0]>L[1]){M1=L[0];M2=L[1];}
else {M1=l[1];M2=L[0];}
}
else{
//分而治之,把L划分为长为n/2的L1,L2
MAXMIN(L1,n/2,M11,M21);
MAXMIN(L2,n/2,M12,M22);
M1=MAX(M11,M12);
M2=MIN(M21,M22);
}
}
楼主可以自己证明
T(n)= 0 n=1
= 1 n=2
= T(n/2)+T(n/2)+2 n>2
结果是，T(n)=1.5n-2
3 楼
lutree1985 [专家分：3490] 发布于 2006-04-07 22:38:00
楼主需要看一些算法方面的书了
呵呵
这是一个已经被证明了的经典的求 max min 的最优算法
我来回复
您所在位置：