采用分治法求含n个实数序列中的最大元素和次大元素（C语言）

目录

实验内容：

实验过程：

1.算法设计

2.程序清单

3.复杂度分析

4.运行结果

实验内容：

设计一个程序，采用分治法求含n个实数序列中的最大元素和次大元素，并分析算法的时间复杂度。

实验过程：

1.算法设计

该程序采用递归分治策略,以下是算法设计思路的详细描述：

核心函数solve()：

• 基本情况：当数组只有一个元素（low == high）时，直接将该元素赋值给max1，将一个较小常数（如-1000）赋值给max2作为初始次大值。若只有两个元素（low == high - 1），则直接比较并返回两元素的最大值和最小值作为最大值和次大值。
• 递归分割：对于包含三个或更多元素的数组，计算中间下标mid，将数组分为左右两个子区间：a[low..mid]和a[mid+1..high]。
• 递归调用：对左右子区间分别调用solve()函数，分别得到左右区间的最大值lmax1和rmax1以及次大值lmax2和rmax2。
• 合并结果：比较左右子区间的最大值lmax1和rmax1，将较大者赋值给全局最大值max1。接着，从剩余元素（包括左右区间的次大值及未被选为最大值的另一区间最大值）中找出最大值，将其赋值给全局次大值max2。

辅助函数：

1. max(int m, int n)：比较两个整数，返回较大的值。
2. min(int m, int n)：比较两个整数，返回较小的值。

主函数main()：

1. 获取用户输入：首先提示用户输入整数数组的元素个数n，然后根据n读取相应的整数元素，依次存入数组a中。
2. 调用solve()函数：传入数组a、起始下标low（设为0）、结束下标high（设为n-1）以及两个引用变量max1和max2用于接收最大值和次大值。
3. 输出结果：在solve()函数执行完毕后，输出最大值max1和次大值max2。

 2.程序清单

#include<stdio.h>
#include <climits>
int max(int m, int n) {
    return (m > n) ? m : n;
}

int min(int m, int n) {
    return (m < n) ? m : n;
}
void solve(int a[],int low,int high,int &max1,int &max2){
	if(low==high){
		max1=a[low];
		max2=-1000;
	}else if(low==high-1){
		max1=max(a[low],a[high]);
		max2=min(a[low],a[high]);
	}else{
		int mid=(low+high)/2;
		int lmax1,lmax2;
		solve(a,low,mid,lmax1,lmax2);//左区间求lmax1,lmax2
		int rmax1,rmax2;
		solve(a,mid+1,high,rmax1,rmax2);//右区间求rmax1,rmax2
		if(lmax1>rmax1){
			max1=lmax1;
			max2=max(lmax2,rmax1);
		}else{
			max1=rmax1;
			max2=max(lmax1,rmax2);
		}
	}
}

int main(){
	int n;
	printf("请输入元素的个数：");
	scanf("%d",&n);
	int a[100];
	printf("请输入元素：\n");
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int max1,max2;
	solve(a,0,n-1,max1,max2);
	printf("最大元素为：%d\n",max1);
	printf("次大元素为：%d\n",max2);
	return 0;
}

3.复杂度分析

(1)时间复杂度

时间复杂度主要是调用solve函数

(2)空间复杂度

实验查找最大值和次大值是在一个一维数组的存储并得出出结果，故采用分治法求含n个实数序列中的最大元素和次大元素的算法空间复杂度为O(n)。

4.运行结果