2.10配列内の最大値と最小値の検索
1,者は2つの独立した問題と見なすことができる.
個はN回比較する必要があり、2*N回比較する必要がある.
2、私たちは2つのグループに分けることができます.
各ペアの中で小さいのは左、大きいのは右です.N/2回.
奇数ビットをN/2回比較し、最小値を見つけます.
偶数ビットをN/2回比較し、最大値を見つけます.
合計比較回数:1.5 N.
欠点:元の配列を破壊しました.
3、2つの変数minとmaxを維持します.
2つの数を取り出し、1回比較します.
minと比較して、minを更新するかどうかを決定します.
同様にmaxを更新します.
2つの数を処理し、3回比較することができます.
合計比較回数:1.5 N
利点:元の配列を破壊しない.
4、思想を分治する
複雑度分析:
f(2) = 1;
f(n) = 2*f(n/2) + 2; (注:1階は2回比較する必要があります)
f(n)=1.5*n-2を出すことができます.
全体の比較回数は減少していないことがわかる.
個はN回比較する必要があり、2*N回比較する必要がある.
2、私たちは2つのグループに分けることができます.
各ペアの中で小さいのは左、大きいのは右です.N/2回.
奇数ビットをN/2回比較し、最小値を見つけます.
偶数ビットをN/2回比較し、最大値を見つけます.
合計比較回数:1.5 N.
欠点:元の配列を破壊しました.
3、2つの変数minとmaxを維持します.
2つの数を取り出し、1回比較します.
minと比較して、minを更新するかどうかを決定します.
同様にmaxを更新します.
2つの数を処理し、3回比較することができます.
合計比較回数:1.5 N
利点:元の配列を破壊しない.
4、思想を分治する
#include <iostream>
using namespace std;
void maxmin(int a[],int low,int high,int& max,int& min) //
{
int k, max1,min1,max2,min2;
if(high-low==1||high-low==0)
{
a[low]>a[high]? (max = a[low], min = a[high]):(max = a[high], min = a[low]);
}
else
{
k=(high+low)/2;
maxmin( a,low,k,max1,min1);
maxmin( a,k+1,high,max2,min2);
//
max=max1>max2? max1:max2;
min=min1<min2? min1:min2;
}
}
int main()
{
int max,min;
int data[]={8,3,6,2,1,9,4,5,7};
int num=sizeof(data)/sizeof(data[0]);
maxmin(data,0,num-1,max,min);
cout<<" :"<<max<<endl;
cout<<" :"<<min<<endl;
return 0;
}
複雑度分析:
f(2) = 1;
f(n) = 2*f(n/2) + 2; (注:1階は2回比較する必要があります)
f(n)=1.5*n-2を出すことができます.
全体の比較回数は減少していないことがわかる.