c语言算法 - 分而治之算法

核心提示：下面进行复杂性分析，注意到当n为偶数时，c语言算法 - 分而治之算法(4)，在for循环外部将执行一次比较而在f o r循环内部执行3(n/2 - 1)次比较，比较的总次数为3 n/2 - 2，比较的总次数为「3n/2ù-2次，程序14-1 找出最小值和最大值的非递归程序templatebool MinM

下面进行复杂性分析。注意到当n为偶数时，在for循环外部将执行一次比较而在f o r循环内部执行3(n/2 - 1)次比较，比较的总次数为3 n/2 - 2。当n为奇数时，f o r循环外部没有执行比较，而内部执行了3(n-1)/2次比较。因此无论n为奇数或偶数，当n>0时，比较的总次数为「3n/2ù-2次。

程序14-1 找出最小值和最大值的非递归程序

template
bool MinMax(T w[], int n, T& Min, T& Max)
{//寻找w [ 0 : n - 1 ]中的最小和最大值
//如果少于一个元素，则返回f a l s e
//特殊情形：n <= 1
if(n < 1)return false;
if(n == 1){Min = Max = 0;
return true;}
//对Min和M a x进行初始化
int s;//循环起点
if(n % 2){//n为奇数
Min = Max = 0;
s = 1;}
else {//n为偶数，比较第一对
if(w[0] > w[1]){
Min = 1;
Max = 0;}
else {Min = 0;
Max = 1;}
s = 2;}
//比较余下的数对
for(int i = s; i < n; i += 2){
//寻找w[i]和w [ i + 1 ]中的较大者
//然后将较大者与w [ M a x ]进行比较
//将较小者与w [ M i n ]进行比较
if(w[i] > w[i+1]){
if(w[i] > w[Max])Max = i;
if(w[i+1] < w[Min])Min = i + 1;}
else {
if(w[i+1] > w[Max])Max = i + 1;
if(w[i] < w[Min])Min = i;}
}
return true;
}