算法设计笔记----递归与分治

一、一些概念

1.递归

​ 直接或者间接地调用自身的算法成为递归。主要是依托于递归函数来实现,递归函数是指用函数自身给出定义的函数。同时,递归也是实现分治的基础,大部分分治算法都是依托于递归来实现的。

2.分治

​ 分治法的设计思想是,将一个难以解决的大问题,分割成一些规模较小的相同问题,以便于各个击破,分而治之。分解后的这些子问题相互独立且与原问题相同,递归的解这些子问题,然后将各个子问题的解进行合并得到原问题的解。分治的核心就在于将问题分解进行简化,往往一个复杂的问题经过分解后,会变得容易解决。

​ 举例,棋盘覆盖问题。便是将一个复杂的n * n情况,分解成最终只有4*4的情况,这种情况下问题就会变得很简单。

二、如何计算分治算法的时间复杂度

​ 假如分治法将一个规模为n的问题分解为k个规模为n/m的子问题去解决,为了方便起见,规定adhoc(指用于直接解小规模的问题P,当P的规模不超过n0时,直接用算法adhoc(P)求解)解规模为1的问题耗费1个时间单位时间。另外,再设将问题分解以及合并解的过程需要f(n)个单位时间。如果用T(n)表示分治算法解规模为n的问题所需时间,则有:

​ 反复代入求解得:

三、应用举例

1.二分搜索

1.1 核心思想

​ 给出一个由n个数组成的数列,在前提是数列有序(一般递增)的情况的,可以应用二分搜索算法。

​ 现在要从这n个元素中找出中找出特定元素x。利用分治的思想,首先我们取元素a[n/2],如果x=a[n/2]则表示已经找到,如果x>a[n/2],因为元素有序,可知x一定在a[0:n-1]的右半部份,我们继续对右半部分进行折半查找,同理,当x<a[n/2]时,我们对左半部分进行二分查找。

​ 这样,最坏情况下用O(logn)时间完成搜索任务。

1.2 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;
int nums[maxn];

//二分搜索过程,递归版
int mid_find(int x,int s,int e){
int length=e-s;
int mid=length/2;
if(nums[mid]==x){
return mid;
}else if(nums[mid]<x){
return mid_find(x,mid+1,e);
}else{
return mid_find(x,s,mid-1);
}
}
//二分搜索过程,循环版
int mid_find2(int x,int left,int right){
while(left<=right){
int mid=(left+right)/2;
if(x==nums[mid])
return mid;
if(x>nums[mid])
left=mid+1;
else
right=mid-1;
}
return -1;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>nums[i];
}
sort(nums,nums+n);
int x;
cin>>x;
int t=mid_find(x,0,n-1);
cout<<t<<" "<<nums[t]<<endl;
return 0;
}

关键点在于中间点位置的确定以及下一次查找时左右边界的确定。

二分搜索还有很多变种问题,比如查找第一个等于key的元素,查找最后一个等于key的元素,查找小于或等于key的元素问题等。

这里可以参考文章:

你真的会写二分查找吗

2.棋盘覆盖问题

2.1 问题描述

在一个2^k * 2^k个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。 如图所示:

现在要用如图所示的四种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何两个L型骨牌不得重叠覆盖。求所需方格数。

其实我们可以发现规律,对于任何一个k阶棋盘,用到的L型骨牌数恰为:(4^k-1)/3,此外我们可以用分治法来解决这个问题。

2.2 算法思想

​ 在n * n的棋盘时我们很难解决这个问题,但是如果我们把他分解成2 * 2的棋盘,这个问题就很容易解决,只需要用一个L型骨牌覆盖不是特殊方格的剩余三个格子即可。我们可以利用分治的思想,将一个n * n棋盘分解成很多四乘四的棋盘。

​ 我们可以将棋盘划分成四个部分,其中一个部分有特殊方格,对于这部分我们继续分治解决。另外三个部分我们可以在他们相邻的角上放一个L型骨牌,然后把L型骨牌所占的格子当作特殊格子,然后继续对这三部分进行分治解决。

​ 如下图所示:

2.3 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int solve(int k,int x,int y){
//cout<<k<<endl;
if(k==1)
return 1;
if(k==0)
return 0;
int len=1<<k;
int x1=len/2;
int y1=len/2;
if(x<=x1&&y<=y1){
int t1=solve(k-1,x,y);
int t2=solve(k-1,x1,y1+1);
int t3=solve(k-1,x1+1,y1);
int t4=solve(k-1,x1+1,y1+1);
return t1+t2+t3+t4+1;
}else if(x<=x1&&y>y1){
int t1=solve(k-1,x1,y1);
int t2=solve(k-1,x,y);
int t3=solve(k-1,x1+1,y1);
int t4=solve(k-1,x1+1,y1+1);
return t1+t2+t3+t4+1;
}else if(x>x1&&y<=y1){
int t1=solve(k-1,x1,y1);
int t2=solve(k-1,x1,y1+1);
int t3=solve(k-1,x,y);
int t4=solve(k-1,x1+1,y1+1);
return t1+t2+t3+t4+1;
}else{
int t1=solve(k-1,x1,y1);
int t2=solve(k-1,x1,y1+1);
int t3=solve(k-1,x1+1,y1);
int t4=solve(k-1,x,y);
return t1+t2+t3+t4+1;
}
return 0;
}
int main(){
int k;
int x,y;
cin>>k>>x>>y; //输入方块的n^k中k的值以及特殊方块所在坐标
int t=solve(k,x,y);
cout<<t<<endl;
return 0;
}

这种算法渐进意义下时间复杂度为T(k)=O(4^k)

k较小的情况下所需时间尚可,较大情况下会耗费很长时间。

3.快速排序

3.1 算法思想

​ 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤为:

  1. 从数列中挑出一个元素,称为”基准”(pivot),
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

3.2 随机化选取

​ 一般快速排序的平均时间复杂度为O(nlogn),但是如果每次都选择最左端的元素作为基准元素的话,有可能出现O(n^2)的时间复杂度,比如数组已经有序的情况。这时我们可以通过rand()函数进行随机选取元素。每次我们在划分前,随机生成一个i,使得left<=i<=right,然后swap(a[left],a[i])。然后再进行划分和排序即可。

3.3 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10010;
int a[maxn];
//使得x左右两侧分别小于x和大于x
int mid_quic_sort(int l,int r){
int x=a[l];
int i=l;
int j=r+1;
while(true){
while(a[++i]<x&&i<r);
while(a[--j]>x);
if(i>=j)
break;
//swap(a[i],a[j]);
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
a[l]=a[j];
a[j]=x;
return j;
}
//随机选取
void randoms(int l,int r){
int p=rand()%(r-l+1)+l;
int x=a[p];
a[p]=a[l];
a[l]=x;
return;
}
//递归排序
void random_quick_sort(int l,int r){

if(l>=r)
return;
randoms(l,r);
int mid=mid_quic_sort(l,r);
random_quick_sort(l,mid-1);
random_quick_sort(mid+1,r);
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
random_quick_sort(0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}

3.4 快排思想的扩展:寻找第K大数

​ 利用快排的思想,我们可以提供一种解决寻找第k大数的方法。快速排序在排序的过程中,有一部是根据划分数将比划分数小的放到划分数左边,大的放到划分数右边,另外得到划分数的位置k’。这样如果k’=k,我们就找到了第k大的数。

​ 一下是算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
void random_quick_sort(int l,int r,int k){

if(l>=r)
return;
randoms(l,r);
int mid=mid_quic_sort(l,r,k);
if(mid==k)
return mid;
else if(mid>k)
return random_quick_sort(l,mid-1,k);
else
random_quick_sort(mid+1,r,k);
}

只需要简单变形即可。