实验原理
利用分治法查找数组元素的最大值与最小值。并计算出程序运行所需要的时间。
实验步骤
①将问题分解，如果数组中只有一个元素，那么只需要比较该元素与当前的最大值最小值并进行更新即可
②将问题扩大，数组中有多个元素，则可以通过套用二分法进行拆分，递归将整个数组拆分为多个只有一个元素的小数组，即分解为多个1问题
③最后将每一个小数组得到的结果进行比较，选取其中的最大值和最小值对存储最大值最小值的变量进行更新
关键代码
template<class type>//为了对任何类型进行比较，实际上只需要为int
int BS(type a[],int left,int right,int & max,int & min){//第一个元素为数组，每次对数组的left和right进行更新，直到二者相等，即当前数组中只有一个元素；max和min为存储最大值和最小值的变量，必须为指针或者引用
int middle,max1,max2,min1,min2;
if(left==right){
max=a[left];
min=a[left];
}else{
middle=(left+right)/2;
BS(a,middle+1,right,max1,min1);
BS(a,left,middle,max2,min2);
if(min1>min2) min=min2;
else min=min1;
if(max2>max1) max=max2;
else max=max1;
}
}
通过代码可以看出时间复杂度近似为nlogn
完整代码
#include <iostream>
#include <fstream>
#include <windows.h>
using namespace std;
template<class type>
int BS(type a[],int left,int right,int & max,int & min);
int main()
{
ofstream out;
out.open("output.txt");
ifstream in;
in.open("input.txt");
int n;
in>>n;
int a[n];
for(int i=0;i<n;i++){
in>>a[i];
}
int max=a[0];
int min=max;
LARGE_INTEGER time,time0,time1,time2;
QueryPerformanceFrequency(&time);
QueryPerformanceCounter(&time0);
BS(a,0,n-1,max,min);
QueryPerformanceCounter(&time1);
out<<"最大值为："<<max<<" 最小值为："<<min<<"时间为："<<1000.0*(time1.QuadPart-time0.QuadPart)/time.QuadPart<<"ms"<<endl;
return 0;
}
template<class type>
int BS(type a[],int left,int right,int & max,int & min){
int middle,max1,max2,min1,min2;
if(left==right){
max=a[left];
min=a[left];
}else{
middle=(left+right)/2;
BS(a,middle+1,right,max1,min1);
BS(a,left,middle,max2,min2);
if(min1>min2)
min=min2;
else
min=min1;
if(max2>max1)
max=max2;
else
max=max1;
}
}
// }
// if(right==left+1){
// if(a[right]>a[left]){
// min=a[left];
// max=a[right];
// }else{
// min=a[right];
// max=a[left];
// }