【精选】算法设计与分析（第三章分治法）

命运之光

发布于 2024-03-20 13:53:23

1050

发布于 2024-03-20 13:53:23

文章被收录于专栏：我在本科期间写的文章

前言

总结算法设计与分析课程期末必记知识点。

第三章分治法

1、分治法概念

分治法是使用最广泛的算法设计方法之一。其基本策略是采用递归思想把大问题分解成一些小问题，然后由小问题的解方便地构造出大问题的解。

2、分治法所能解决的问题一般具有以下几个特征

（1）该问题的规模缩小到一定的程度就可以容易地解决。（2）该问题可以分解为若干个规模较小的相似问题。（3）利用该问题分解出的子问题的解可以合并为该问题的解。（4）该问题所分解出的各个子问题是互相独立的，即子问题之间不包含公共的子问题。

3、分治法的求解过程（简答）

（1）分解成若干个子问题（2）求解子问题（3）合并子问题

4、快速排序（大题）

#include<stdio.h>

void disp(int a[],int n){	//输出 a 中的所有元素 
	int i;
	for(i=0;i<n;i++)
		printf("%d",a[i]);
	printf("\n");
}

int Partition(int a[], int s, int t)	//划分算法
{
	int i = s, j = t;
	int tmp = a[s];						//用序列的第 1 个记录作为基准
	while (i != j)						//从序列两端交替向中间扫描，直到 i=j为止
	{
		while (j > i && a[j] >= tmp)	
			j--;						//从右向左扫描，找第 1 个关键字大于 tmp 的a[i]
		a[i] = a[j];					//将a[i]后移到a[j]的位置
		while (i < j && a[i] <= tmp)
			i++;						//从左向右扫描，找第 1 个关键字大于 tmp 的a[i]
		a[j] = a[i];					//将 a[i]后移到a[j]的位置
	}
	a[i] = tmp;
	return i;
}

void QuickSort(int a[], int s, int t)		//对a[s..t]元素序列进行递增排序
{
	if (s < t)
	{
		int i = Partition(a, s, t);
		QuickSort(a, s, i - 1);				//对左子序列递归排序
		QuickSort(a, i + 1, t);				//对右子序列递归排序
	}
}

int main() {
	int n = 5;
	int a[] = { 5,2,3,1,4 };
	printf("排序前：");
	disp(a, n);
	QuickSort(a, 0, n - 1);
	printf("排序后：");
	disp(a, n);
	return 0;
}

5、冒泡排序和简单选择排序的时间复杂度

冒泡排序：时间复杂度O(n^2) 简单选择排序：时间复杂度 O（n^2）

6、快速排序的时间复杂度

时间复杂度

7、自顶向下的二路归并排序算法

void MergeSort(int a[], int low, int high)	//二路归并算法
{
	int mid;
	if (low < high)							//子序列有两个或两个以上元素
	{
		mid = (low + high) / 2;				//取中间位置
		MergeSort(a, low, mid);				//对a[low..mid]子序列排序
		MergeSort(a, mid + 1, high);		//对a[mid+1..high]子序列排序
		Merge(a, low, mid, high);		//将两个子序列合并，见前面的算法
	}
}

时间复杂度为

8、折半查找算法

#include<stdio.h>
int BinSearch(int a[], int low, int high, int k)//折半查找算法
{
	int mid;
	if (low <= high)			//当前区间存在元素时
	{
		mid = (low + high) / 2; //求查找区间的中间位置
		if (a[mid] == k)			//找到后返回其物理下标mid
			return mid;
		if (a[mid] > k)				//当a[mid]>k时在a[low..mid-1]中递归查找
			return BinSearch(a, low, mid - 1, k);
		else                        //当a[mid]<k时在a[mid+1..high]中递归查找
			return BinSearch(a, mid + 1, high, k);
	}
	else return -1;					//当前查找区间没有元素返回-1
}
int main() {
	int n = 10, i;
	int k = 6;
	int a[] = { 1,2,3,4,5,6,7,8,9,10 };
	i = BinSearch(a, 0, n - 1, k);
	if (i >= 0)
		printf("a[%d]=%d\n", i, k);
	else
		printf("未找到%d元素\n", k);
	return 0;
}