递归和分治

分治法

顾名思义，“分而治之”的思想，把一个复杂的问题分成两个或更多或相似的子问题，在把子问题分成更小的子问题，直到最后子问题可以直接求解，原问题的解即子问题的解的合并。

算法步骤

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
求解：若子问题规模较小而容易被解决则直接解，否则，递归地解各个子问题。
合并：将各个子问题的解合并为原问题的解。

常见题目

二分查找

算法步骤

首先确定数组中间下标， $mid=(left+right)/2$
然后让需要找的数 $x$ 和数组 $A[mid]$ 作比较

如果 $x \gt A[mid]$ ，说明要找的数在 $mid$ 右边，因此需要递归向右查找。
如果 $x \lt A[mid]$ ，说明要找的数在 $mid$ 左边，因此需要递归向左查找。
如果 $x = A[mid]$ ，说明要找到了 $x$ ，返回下标。

A数组是要求有序的。

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

时间复杂度：

T_n = \left\{\begin{matrix} O(1) \space, n=1 \\ 1 \cdot T(n/2) + O(1) \space, n\gt1 \end{matrix}\right.

化简即： $O(log_2n)$

大整数的乘法

题目：
有 $X、Y$ 是 $n$ 位二进制数，现计算 $X、Y$ 乘积
算法分析：
将二进制整数 $X$ 和 $Y$ 各分为2段，每段长 $n/2$ 位，假设 $n$ 是2的次幂。

X=A2^\frac{n}{2}+B

Y=C2^\frac{n}{2}+D

XY=AC2^n+(AD+BC)2^\frac{n}{2}+BD

有四次 $\frac{n}{2}$ 为大整数相乘，3次加法，2次移位运算。
时间复杂度：：

T_n = \left\{\begin{matrix} O(1) \space, n=1 \\ 4 \cdot T(n/2) + O(n) \space, n\gt1 \end{matrix}\right.

化简下来和传统的时间复杂度一致为： $O(n^2)$
算法优化：
将上式中的 $AD+BC$ 合并变成 $(A-B)(D-C)+AC+BD$
这样所有的 $\frac{n}{2}$ 乘法次数只有3次，6次加减法，2次移位

XY=AC2^n+((A-B)(D-C)+AC+BD)^\frac{n}{2}+BD

时间复杂度：：

T_n = \left\{\begin{matrix} O(1) \space, n=1 \\ 3 \cdot T(n/2) + O(n) \space, n\gt1 \end{matrix}\right.

化简下来的时间复杂度为： $O(n^{log_23})$
代码：

#include <bits/stdc++.h>
using namespace std;
#define SIGN(A) ((A > 0) ? 1 : -1) 

int mult(int X, int Y, int n) {
	int sign = SIGN(X) * SIGN(Y);
	int x = abs(X);
	int y = abs(Y);
	if (x == 0 || y == 0) {
		return 0;
	} else if (n == 1) {
		return sign * x * y;
	} else {
		int A = (int) x / pow(2, (int)(n/2));
		int B = x - A * pow(2, (int)(n/2));
		int C = (int) y / pow(2, (int)(n/2));
		int D = y - C * pow(2, (int)(n/2));
		int AC = mult(A, C, n / 2);
		int BD = mult(B, D, n / 2);
		int ABDC = mult((A-B), (D-C), n / 2) + AC + BD;
		return sign * (AC * pow(2, n) + ABDC * pow(2, (n/2)) + BD);
	}
}


int main() {
	
	int x, y;
	cin >> x >> y >> n;
	cout << mult(x, y, n);
	return 0;
}

矩阵相乘

题目：
$A、B$ 是 $n$ 阶方阵，计算矩阵乘积。
算法分析：
将 $A、B$ 分割成 $4$ 块大小一样的子矩阵，大小为 $(n/2)*(n/2)$ 的方阵。

\begin{bmatrix} C_{11} & C_{12}\\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12}\\ B_{21} & B_{22} \end{bmatrix}

即得：

C_{11} = A_{11}B_{11}+A_{12}B_{21} \\ C_{12} = A_{11}B_{12}+A_{12}B_{22} \\ C_{21} = A_{21}B_{11}+A_{22}B_{21} \\ C_{22} = A_{21}B_{12}+A_{22}B_{22} \\

总共需要8次乘法，4次加法
时间复杂度：：

T_n = \left\{\begin{matrix} O(1) \space, n=2 \\ 8 \cdot T(n/2) + O(n^2) \space, n\gt2 \end{matrix}\right.

化简下来的时间复杂度为： $O(n^{2})$
算法优化：
经过Strassen优化，只需7次乘法，18次加法
时间复杂度：：

T_n = \left\{\begin{matrix} O(1) \space, n=2 \\ 7 \cdot T(n/2) + O(n^2) \space, n\gt2 \end{matrix}\right.

化简下来的时间复杂度为： $O(n^{log_27})$

棋盘覆盖

算法步骤：

将当前棋盘4等分
判断特殊方格所在区域
往无特殊方格区域的特定位置添加特殊方格
重复以上三步，直到方格为1x1无法划分

代码：

#include <bits/stdc++.h>
using namespace std;



/*
tr 子棋盘左上角行坐标
tc 子棋盘左上角列坐标
dr 特殊方格行坐标
dc 特殊方格列坐标
size 棋盘行或列长度，应为2的n次方
棋盘board从0，0开始

左上角 dr < tr + size      dc < tc + size
右上角    <                   >=
左下角    >=                  < 
右下角    >=                  >= 
*/

int t = 1; //骨牌编号
int board[100][100];

void chessBoard(int tr, int tc, int dr, int dc, int size) {
	if (size == 1) {
		return ;
	}
	int tile = t ++; //L型骨牌编号
	size /= 2;	//分割棋盘
	
	//左上角
	if (dr < tr + size && dc < tc + size) { 
		//特殊方格在左上区域 
		chessBoard(tr, tc, dr, dc, size);
	} else { //如果不在左上区域，就把右下角格子设置为特殊方格
		//用tile号L型骨牌覆盖右下角 
		board[tr + size - 1][tc + size - 1] = tile;
		chessBoard(tr, tc, tr + size - 1, tc + size - 1, size);
	}
	//右上角 
	if (dr < tr + size && dc >= tc + size) {
		//特殊方格在右上区域  
		chessBoard(tr, tc + size, dr, dc, size);
	} else {//如果不在右上区域，就把左下角格子设置为特殊方格 
		//用tile号L型骨牌覆盖左下角 
		board[tr + size - 1][tc + size] = tile;
		chessBoard(tr, tc + size, tr + size - 1, tc + size, size);
	}
	//左下角
	if (dr >= tr + size && dc < tc + size) {
		//特殊方格在左下区域 
		chessBoard(tr + size, tc, dr, dc, size);
	} else {//如果不在左下区域，就把右上角格子设置为特殊方格
		//用tile号L型骨牌覆盖右上角 
		board[tr + size][tc + size - 1] = tile;
		chessBoard(tr + size, tc, tr + size, tc + size - 1, size);
	}
	//右下角 
	if (dr >= tr + size && dc >= tc + size) {
		//特殊方格在右下区域 
		chessBoard(tr + size, tc + size, dr, dc, size);
	} else {//如果不在右下区域，就把左上角格子设置为特殊方格
		//用tile号L型骨牌覆盖左上角 
		board[tr + size][tc + size] = tile;
		chessBoard(tr + size, tc + size, tr + size, tc + size, size);
	}
}

int main() {
	chessBoard(0, 0, 3, 1, 4);
	for (int i = 0; i < 4; i ++) {
		for (int j = 0; j < 4; j ++) {
			cout << board[i][j] << " ";
		}
		cout << endl;
	}
	
	return 0;
}

时间复杂度：：

T_k = \left\{\begin{matrix} O(1) \space, k=0 \\ 4 \cdot T(k-1) + O(1) \space, k\gt0 \end{matrix}\right.

化简下来的时间复杂度为： $O(4^{k})$

合并排序

算法思想：

不断的将数组分割成较小的子数组，直到每个子数组只有一个元素，这一个元素是有序的
将排好的子数组合并在一起，产生较大的有序子数组
将分割和合并的过程一直重复，直到整个数组都排序完毕

代码：

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1005];
int temp[1005];

void merge_sort(int a[], int l, int r) {
	//只剩一个元素的时候，已经有序，返回
	if (l >= r)	return ;
	
	// 寻找数组中间点下标 
	int mid = (l + r) / 2;
	//递归左半边排序
	merge_sort(a, l, mid);
	//递归右半边排序
	merge_sort(a, mid + 1, r);
	
	//合并排序好的两个数组
	int k = 0;
	//i:左半边数组的下标，j:右半边数组的下标
	int i = l, j = mid + 1;
	while(i <= mid && j <= r) {
		if (a[i] < a[j])
		//左边元素放如临时数组并移动下标
			temp[k ++] = a[i ++];
		else
		//右边元素放入临时数组并移动下标 
			temp[k ++] = a[j ++];
	} 
	//如果左边数组有剩余，则放入临时数组
	while(i <= mid)	temp[k ++] = a[i ++];
	//如果有边数组有剩余，则放入临时数组
	while(j <= r)	temp[k ++] = a[j ++];
	//把临时数组中的元素拷贝至原数组
	k = 0;
	for (int i = l; i <= r; i ++) {
		a[i] = temp[k ++];
	}
}

int main() {
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    //调用算法
    merge_sort(a, 0, n-1);
    //输出到答案
    for(int i = 0; i < n; i++){
        cout<<a[i]<<" ";
    }
	return 0;
}

时间复杂度：：

T_n = \left\{\begin{matrix} O(1) \space, n=0 \\ 2 \cdot T(n/2) + O(n) \space, k\gt0 \end{matrix}\right.

化简下来的时间复杂度为： $O(nlogn)$

快速排序

算法思想：

选择第一个数为基准数
移动元素，使得基准数左边都小于它，右边都大于它。
重复步骤1,2，直到还剩下1个元素。

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1005];

void quick_sort(int a[], int l, int r) {
	if (l >= r)	return ;
	 
	int i = l, j = r;
	int temp = a[l];
	while(i < j) { 
		while(i < j && a[j] >= temp)
			j --;
		//在后面找到比基准值要小的，放到前面 
		if (i < j) {
			a[i] = a[j];
			i ++;
		}
		while(i < j && a[i] < temp)
			i ++;
		//在前面找到比基准值要大的，放到后面
		if (i < j) {
			a[j] = a[i];
			j --;
		}	
	}
	a[i] = temp;
	quick_sort(a, l, i - 1);
	quick_sort(a, i + 1, r);
} 


int main() {
	cin>>n;
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    //调用算法
    quick_sort(a, 0, n-1);
    //输出到答案
    for(int i = 0; i < n; i++){
        cout<<a[i]<<" ";
    }
	
	return 0;
}

链表实现快排：

// 快速排序算法中的划分函数
LNode* partition(LNode* low, LNode* high) {
	int pivot = low->data;// 选择基准值为低指针所指节点的数据
	LNode* p = low;// p是用于标记小于基准值的部分的指针
	LNode* q = low->next;// q是用于遍历链表的指针
	
	while(q != high) {
		if (q-> data < pivot) {
			// 如果当前节点的数据小于基准值，交换p和q所指节点的数据
			p = p -> next;
			swap(p->data, q->data);
		}
		q = q -> next;
	}
	// 将基准值交换到正确的位置上
	swap(p->data, low->data);
	return p;// 返回基准值的新位置
}

void quickSort(LNode* l, LNode* r) {
	if (l != r && l->next != r) {
		// 对当前划分进行排序
		LNode* pivot = partition(l, r);
		// 分别对基准值左右两边的部分进行递归排序
		quickSort(l, pivot);
		quickSort(pivot->next, r);
	}
}

时间复杂度：：
平均时间复杂度为： $O(nlogn)$
最坏时间复杂度为： $O(n^2)$

线性时间选择

题目：
找到一组数中第k小的元素。
算法分析：
每次随机选择基准，只对划分出的子数组之一进行递归处理。

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100005];

int randomQuickSort(int a[], int p, int r) {
	srand((unsigned)time(0));
	int key = rand()%(r - p) + p;
	
	int temp = a[key], i = p, j = r;
	swap(a[key], a[p]);
	while(i < j) { 
		while(i < j && a[j] >= temp)
			j --;
		//在后面找到比基准值要小的，放到前面 
		if (i < j) {
			a[i] = a[j];
			i ++;
		}
		while(i < j && a[i] < temp)
			i ++;
		//在前面找到比基准值要大的，放到后面
		if (i < j) {
			a[j] = a[i];
			j --;
		}	
	}
	a[i] = temp;
	return i;
} 


int select(int a[], int p, int r, int k) {
	if (p == r)	return a[p];
	//一次快速排序，随机选择基准元素，划分数组
	int i = randomQuickSort(a, p, r);
	int j = i - p + 1;// j为a[p,i]中元素个数
	if (k <= j)
		return select(a, p, i, k);
	else
		return select(a, i + 1, r, k - j);//返回第k-j小元素
}


int main() {
	int k;
	scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    //调用算法
    select(a, 0, n-1, k);
    //输出到答案
    cout << a[k - 1] << endl;
	
	return 0;
}

循环赛的日程安排

#include <bits/stdc++.h>
using namespace std;

int a[50][50];

void merge(int n) {
	int m = n / 2;
	for (int i = 1; i <= m; i ++) {
		for (int j = 1; j <= m; j ++) {
			a[i][j + m] = a[i][j] + m;
			a[i + m][j] = a[i][j + m];
			a[i + m][j + m] = a[i][j];
		}
	}
}


void schedule(int n) {
	if (n == 1) {
		a[n][n] = 1;
		return ;
	}
	schedule(n / 2);
	merge(n);
}


int main() {
	
	int n;
	cin >> n;
	schedule(n);
	for(int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			cout << a[i][j];
		}
		cout << endl;
	}
	return 0;
}