Java教程

算法设计与分析递归与分治思维导图和总结

本文主要是介绍算法设计与分析递归与分治思维导图和总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在这里插入图片描述
主定理:
在这里插入图片描述
**

1、二分查找

**
问题描述:
在一有序数组T[ l…r ]中查找x,如果x在T中,输出x在T中的下标j,否则输出-1
基本思想
1、如果l > r,则查找结束,x不在数组中,返回-1,否则将x与中间元素T[mid]比较,如果相等,则返回mid
2、如果x比T[mid]小,则到T[ l…mid-1]进行查找
3、否则到T[mid+1…r ]查找
实现

int BinarySearch(int a[], int x, int n)
{
	int l = 0, r = n - 1;
	while(l <= r)
	{
		int mid = (l + r) / 2;
		if(x == a[mid]) return mid;
		if(x > a[mid]) l = mid + 1;
		if(x < a[mid]) r = mid - 1;
	}
	return -1;
}

2、大整数乘法

问题描述
设X和Y都是n位整数,现在要计算他们的乘积XY
基本思想
将每个大整数串分成等分成两个长度近似的字串,例如A分成A1和A2,Y分成B1和B2
则A * B = (A1 * 10^(n/2) + A2)(B1 *10^(m/2) + B2)
化简得 A1B1 * 10^n + (A1B2 + A2B1)*10^(n/2) + A2B2
XY = A1B1 * 10^n + ((A1-A2)(B2-B1) + A1B1 + A2B2) * 10^(n/2) + A2B2
时间复杂度
T(n) = 3T(n / 2) + O(n)
通过主定理可算出T(n) = O(n^1.59)

3、Strassen矩阵乘法

题目描述
设A、B是两个n*n的矩阵,计算它们的乘积AB
基本思想
使用分治法,将一个矩阵转换为子矩阵相乘的方式。矩阵乘法耗费时间要比矩阵加法耗费的时间多,想要改进矩阵乘法的计算时间复杂性,必须减少乘法运算。Strassen矩阵乘法用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。时间复杂度优化到O(n^2.81)
在这里插入图片描述在这里插入图片描述

4、棋盘覆盖

问题描述
在一个2^k * 2^k个方格组成的棋盘中,恰有一个方格与其它方格不同,则称方格为一特殊方格,且称该棋盘为一特殊棋盘。现在要用四种方向不同的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格。
基本思想
用分治策略,当k>0时,将棋盘分割为4个子棋盘。特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将原问题转化为4个较小规模的相同覆盖问题。时间复杂度T(k)=4T(k-1)+O(1)
在这里插入图片描述在这里插入图片描述

5、快速排序

基本思想
快速排序使用分治的思想,通过一趟排序将待排序列分割成两部分,其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
具体步骤
(1)选择基准:在待排序列中,按照某种方式挑出一个元素,作为 “基准”(pivot)
(2)分割操作:以该基准在序列中的实际位置,把序列分成两个子序列。此时,在基准左边的元素都比该基准小,在基准右边的元素都比基准大
(3)递归处理:递归地对两个序列进行快速排序,直到序列为空或者只有一个元素。
选择基准的方式:
(1)固定位置
取序列的第一个元素或中间元素作为基准
(2)随机化选择(随机化快排)
随机取一个元素作为基准
让随机出来的下标对应数字作为pivot,减小了一般快排出现最坏情况的可能性。
复杂度分析
最坏时间复杂度: O(n^2)
最好时间复杂度: O(nlogn)
平均时间复杂度: O(nlogn)

void quicksort(int q[], int l, int r)
{
	if(l >= r) return;
	int x = q[(l + r) / 2];
	int i = l - 1, j = r + 1;
	while(i < j)
	{
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if(i < j)  swap(q[i],q[j]);	
	}
	quicksort(q, l, j);
	quicksort(q, j+1, r);
}

随机化

void quicksort(int q[], int l, int r)
{
	if(l >= r) return;
	int i = l - 1, j = r + 1;
	int tt = rand() % (r - l + 1) + l;
	int x = q[tt];
	swap(q[l],q[tt]);
	while(i < j)
	{
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if(i < j)  swap(q[i],q[j]);	
	}
	quicksort(q, l, j);
	quicksort(q, j+1, r);
}

6、合并排序

基本思想
将序列大致分成两个大小大致相等的子序列,直到序列只有一个元素,然后再将排好序的子序列合并成为一个排好序的序列。复杂度O(NlogN)
代码实现

void MergeSort(int a[], int l, int r)
{
	if(l >= r) return;
	int mid = (l + r) / 2;
	MergeSort(q, l, mid);
	MergeSort(q, mid+1, r);
	int k = 0, i = l, j = mid + 1;
	while(i <= mid && j <= r)
	{
		if(a[i]<a[j]) tmp[k++] = a[i++];
		else tmp[k++] = a[j++];
	}
	while(i <= mid) tmp[k++] = a[i++];
	while(j <= r)   tmp[k++] = a[j++];  
	for(i=l , j =0; i <= r ;i++, j++ )
	    a[i] =  tmp[j];
	
}

7、求第k小数(线性时间)

基本思想
1、将n个元素划分成 ⌈ n / 5 ⌉ \lceil n/5 \rceil ⌈n/5⌉组,每组5个元素,至多只有一组包含n mod 5个元素
2、通过每组排序,找出每组的中位数构成序列M
3、取序列M的中位数x(若序列有偶数,取两个中位数中较大者)
4、用x作为基准元素,对原n个元素进行划分,i为分裂点
5、若k<=j,则用前部分子问题递归求第k小元素;
若k>j,则用后部分子问题求第k-i小元素
j为前部分子问题元素的个数。

8、平面最接近点对问题

基本思想
1、将点集分成大致相等的两个部分A和B
2、递归分别求解A和B种的最近点对d1和d2
3、再求出一点在A中、另一点在B中的最近点对d12
4、原问题的解d = min{d1,d2,d12}
AB连接部分产生最近点对情况:只会发生在 ( mid - d , mid + d ) 内,这个范围,mid左边p1,mid右边p2,p1中每个点最多在p2中存在6个点会更新答案,即按照y坐标排序后,p1每点最多只要检查p2中排好序的相继6个点。

9、循环赛日程表

题目描述
设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次
(2)每个选手一天只能赛一次
(3)循环赛一共进行n-1天
基本思想
按照分治思想,将所有的参赛选手分成两半,n个选手的日程表就可以通过n/2个选手设计的比赛日程表来确定。递归进行分割,直到剩下两个选手即可。

这篇关于算法设计与分析递归与分治思维导图和总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!