分治算法简单介绍

x33g5p2x  于2022-04-10 转载在 其他  
字(2.1k)|赞(0)|评价(0)|浏览(586)

分治策略的基本思想

基本思想

将一个难以直接解决的大问题,分解成一些规模较小的相同的子问题,各个问题相互独立;递归地解决各个子问题,将子问题的解归并成原问题的解

分治策略

  1. 将原始问题划分或者归结为规模较小的子问题
  2. 递归或者迭代求解每个子问题
  3. 将子问题的解 综合 或者 不综合 得到原问题的解

注意

  1. 子问题和原问题性质完全一样
  2. 子问题之间可彼此独立地求解
  3. 递归停止时子问题可直接求解

二分查找

设计思想:

  • 通过x与中位数比较,将原问题归结为规模减半的子问题,对子问题进行二分检索
  • 当子问题规模为1时,继续比较x与T[m],若相等则返回m,否则返回特殊值
    非递归写法:

BinarySearch(T,l,r,x)
T:数组l:左边界r:右边界x:目标数

伪代码:

l <- 1; r <-n;
while l<=r do
	m <- [(l+r)/2]	// m为中间位置
	if T[m] = x then return m	// 中位数就是目标值,直接返回中位数下标
	else if T[m] > x then r <- m-1
	else l <- m+1

return 0

递归写法:

BinarySearch(s[n],x,int low, int high)
s[n]:数组x:目标数low:左边界high:右边界

输入:查找序列s,要查找的元素x,查找范围
输出:查找结果:元素所在位置 或 -1

伪代码:

if(low < high) then return -1;
middle <- (low+high)/2;	// 分解
if(x=s[middle]) then return middle;
else if(x>s[middle]) then
	return BinarySearch(s,x,middle+1, high);
else 
	return BinarySearch(s,x,low, middle-1);

使用递归的话,时间复杂度为O(logn),空间复杂度为O(logn)(由于递归深度是O(logn))

循环赛日程表

题目:

2个运动员:

4个运动员:

8个运动员:

伪代码:

算法: arrange(p, q, n, arr), 其中 n=2^k
输入:子问题的位置(p,q), 子问题的规模n,循环赛日程表arr[0][i]。这里==(p,q)是左上角的坐标==
输出:arr[][]

if(n>1) then
{
	arrange(p, q, n/2, arr)		// 左上角递归
	arrange(p, q+n/2, n/2, arr)		// 右上角递归
}

for i<- p+n/2 to p+n do				// 右上 拷贝到 左下
	for j<- q to q+n/2 do
	arr[i][j] <- arr[i-n/2][j+n/2]

for i<- p+n/2 to p+n do				// 左上 拷贝到 右下
	for j<- q+n/2 to q+n do
	arr[i][j] <- arr[i-n/2][j-n/2]

return arr

为了方便,其实我们实际代码编写的时候,并非按照我们上边介绍的那样 左上 -> 右下, 右上 -> 左下
而是按照 1、右上 -> 左下 2、左上 -> 右下 的顺序

时间复杂度 O(n^2)
空间复杂度 O(logn)

归并排序

详细可以看我这篇文章:【八大排序算法】
算法思想:
合并排序是采用分治策略实现对n个元素进行排序的算法,采用二分分治策略

  1. 分解:将待排序元素分为大小大致相同的两个子序列,从中间一份二
  2. 合并:分别对两个子序列递归,将排好序的两个子序列进行合并,得到一个有序序列

C++代码实现:

主方法MergeSort

合并方法Merge(核心逻辑):

时间复杂度 O(nlogn)
空间复杂度 O(n)(需要临时数组,以及栈空间)

快速排序

  • 分:选定一个元素作为基准元素,小于基准元素的放左边,大于基准元素的放右边
  • 递归求解子问题

详细可以看我这篇文章:【八大排序算法】

书上伪代码:(这个效率不是太高哈)
算法Quicksort(A, p, r) // p, r为待排序元素下标
输入:数组A[p…r]
输出:排好序的数组A

Quicksort:

if p<r
then q <- Partition(A,p,r)	// 划分后返回q为基准的位置
A[p] <-> A[q]	// 首元素和对应位置元素交换
Quicksort(A,p,q-1)
Quicksort(A,q+1,t)

初始值 p=1, r=n

Partition方法:

改进版:(了解即可)

交换不正确元素的位置,我们只交换 左边不符合的值右边不符合的值,这样就不需要再与轴点去交换了,减少不必要的交换次数

Partition(A,p,r)从左右两方扫描,交换不正确位置的元素,直到扫描结束,将基准元素换到正确的位置
输入:数组A[p,r]
输出: j,(基准元素在排好序的数组中的位置)

Partition(A,p,r)伪代码:

x <- A[p]
i <- p
j <- r+1
while true do
	repeat j <- j-1
	until A[j] <= x		// 不超过基准元素的
	repeat i <- i+1
	until A[i] > x		// 比基准元素大的
	if i<j
	then A[i] <-> A[j]
	else return j

最坏时间复杂度O(n^2)

子问题划分的越均匀,时间复杂度越好

平均时间复杂度O(nlogn)

相关文章