分治法

分治法：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：

1. 分解原问题为若干个子问题，这些子问题是原问题的规模较小的实例。
2. 解决这些子问题，递归地求解各个子问题。然而，若子问题的规模足够小，则直接求解。
3. 合并这些子问题的解成原问题的解。

归并排序

归并排序完全遵循分治模式：

1. 分解：分解待排序的n个元素的序列成各具$n/2$n/2个元素的两个子序列。
2. 解决：使用归并排序递归地排序两个子序列。
3. 合并：合并两个已排序的子序列以产生答案。

下图是归并排序排序一个数组的过程：

先自顶向下分解问题，再自底向上解决问题。

使用一个方法来合并已排序的子序列。伪代码：


java代码实现：

	private static void merge(int[] a, int p, int q, int r) {
		int[] left = new int[q - p + 1];
		int[] right = new int[r - q];
		
		for (int i = 0; i < left.length; i++) {
			left[i] = a[p + i];
		}
		
		for (int j = 0; j < right.length; j++) {
			right[j] = a[q + j + 1];
		}
		int i = 0, j = 0;
		while (p <= r) {
			if (left[i] <= right[j]) {
				a[p++] = left[i++];
				if (i == left.length) {
					for (;j < right.length; j++) {
						a[p++] = right[j];
					}
					break;
				}
			} else {
				a[p++] = right[j++];
				if (j == right.length) {
					for (;i < left.length; i++) {
						a[p++] = left[i];
					}
					break;
				}
			}
		}
	}

接下来把问题分解成子问题并递归调用算法：

	public static void sort(int[] a) {
		sort(a, 0, a.length - 1);
	}
	
	public static void sort(int[] a, int p, int r) {
		if (p < r) {
			int q = (p + r) / 2;
			sort(a, p, q);
			sort(a, q + 1, r);
	        if (a[q] <= a[q + 1]) {
	            return;
	        }
			merge(a, p, q, r);
		}
	}

分析分治算法

当一个算法包含对其自身的递归调用时，我们往往可以用递归方程或递归式来描述其运行时间，该方程根据在较少输入上的运行时间来描述在规模为n的问题上的总运行时间。

分治算法运行时间的递归式来自基本模式的三个步骤。若问题规模足够小，如对某个常量$c$c，$n \leq c$n≤c,则直接求解需要常量时间。我们将其写作$\Theta(1)$Θ(1)。假设把原问题分解成$a$a个子问题，每个子问题的规模是原问题的$1/b$1/b。为了求解一个规模为
$n/b$n/b的子问题，需要$T(n/b)$T(n/b)，所以需要$aT(n/b)$aT(n/b)的时间来求解$a$a个子问题。如果分解问题成子问题需要时间$D(n)$D(n)，合并子问题的解为原问题的解需要时间$C(n)$C(n)，那么得到递归式:

$T_{n}=\begin{cases}\Theta(1)& \text{若}n \leq c \\aT(n/b)+D(n)+C(n)& \text{其他}\end{cases}$Tn​={Θ(1)aT(n/b)+D(n)+C(n)​若n≤c其他​

归并排序算法的分析

在归并排序中，根据分治模式进行分析：

1. 分解：分解步骤仅仅计算子数组的中间位置，需要常量时间，因此$D(n)=\Theta(1)$D(n)=Θ(1)。
2. 解决：我们递归地求解两个规模均为n/2的子问题，将需要$2T(n/2)$2T(n/2)的运行时间。
3. 合并：merge方法需要$\Theta(n)$Θ(n)的时间，所以$C(n)=\Theta(n)$C(n)=Θ(n)。

把$D(n)$D(n)跟$C(n)$C(n)相加后依旧是一个线性函数，即$\Theta(n)$Θ(n)，相当于忽略掉每次分解需要的常数时间，给出归并排序的最坏情况运行时间$T(n)$T(n)的递归式：
$T_{n}=\begin{cases}\Theta(1)& \text{若}n = 1 \\2T(n/2)+\Theta(n)& \text{若}n > 1\end{cases}$Tn​={Θ(1)2T(n/2)+Θ(n)​若n=1若n>1​

根据该递归式，可以得出归并排序算法的时间复杂度为$\Theta(nlog_2n)$Θ(nlog2​n)，其推导过程如下：
$\begin{aligned} T(n)=& 2*T(n/2) + n\\ =& 2*(2*T(n/4) + n/2) + n\\ =& 4*(2*T(n/8) + n/4) + 2n\\ =& ... ...\\ =& 2^k * T(n/2^k) + k*n \end{aligned}$T(n)=====​2∗T(n/2)+n2∗(2∗T(n/4)+n/2)+n4∗(2∗T(n/8)+n/4)+2n......2k∗T(n/2k)+k∗n​

可知$T(1) = \Theta(1)$T(1)=Θ(1) ,那么$T(n/2^{log_2n}) = \Theta(1)$T(n/2log2​n)=Θ(1)，当$k=log_2n$k=log2​n时，
$T(n) = n + nlog_2n$T(n)=n+nlog2​n
所以归并排序算法的时间复杂度为$\Theta(nlog_2n)$Θ(nlog2​n)。

练习题

答：略

答：上面的java代码就是这样实现。

答：
当$n=2$n=2时，$T(2) = 2 log_22 = 2$T(2)=2log2​2=2，结论成立。
当$n=2^k$n=2k时，我们假设结论成立，即$T(2^k)=2^klog_22^k$T(2k)=2klog2​2k。
如果$n=2^{k+1}$n=2k+1时，结论也成立，那么递归式的解就是$T(n)=nlog_2n$T(n)=nlog2​n。
根据递归式：
$\begin {aligned} T(2^{k+1})= &2*T(2^k)+2*2^k\\ = &2(2^klog_22^k) + 2*2^k\\ = &2^{k+1}log_22^k + 2^{k+1}\\ = &2^{k+1}(log_22^k + log_22)\\ = &2^{k+1}log_22^{k+1} \end {aligned}$T(2k+1)=====​2∗T(2k)+2∗2k2(2klog2​2k)+2∗2k2k+1log2​2k+2k+12k+1(log2​2k+log2​2)2k+1log2​2k+1​
也就是当$T(2^k)$T(2k)成立时，$T(2^{k+1})$T(2k+1)也成立。所以可以得出结论$T(n)=nlog_2n$T(n)=nlog2​n成立。

答：
$T_{n}=\begin{cases}\Theta(1)& \text{若}n = 1 \\T(n-1)+\Theta(n)& \text{若}n > 1\end{cases}$Tn​={Θ(1)T(n−1)+Θ(n)​若n=1若n>1​

计算其时间复杂度：
$\begin{aligned} T(n)= &T(n-1) + n\\ = &T(n-2) + 2n\\ = &T(n-3) + 3n\\ = &... ...\\ = &T(n-k) + k*n \end{aligned}$T(n)=====​T(n−1)+nT(n−2)+2nT(n−3)+3n......T(n−k)+k∗n​
当$k=n$k=n时，$T(n)=1+n^2$T(n)=1+n2,所以递归实现的插入排序的时间复杂度为$\Theta(n^2)$Θ(n2)。

java实现：

	public static void sort(int[] a, int tail) {
		if (tail > 0) {
			sort(a, tail - 1);
			int key = a[tail];
			int j = tail - 1;
			for (; j >= 0 && key < a[j]; j--) {
				a[j + 1] = a[j];
			}
			a[j + 1] = key;
		}
	}

答：

伪代码：

search(a, lo, hi, k)
if lo > hi 
	return -1
int mi = (lo + hi) / 2
if k < a[mi] 
	return search(a, lo, mi - 1, k);
else if k > a[mi]
	return search(a, mi + 1, hi, k);
else 
	return mi;

java实现：

public static int search(int[] a, int k) {
	return search(a, 0, a.length - 1, k);
}

private static int search(int[] a, int lo, int hi, int k) {
	if (lo > hi) return -1;
	int mi = (lo + hi) / 2;
	if (k < a[mi]) {
		return search(a, lo, mi - 1, k);
	} else if (k > a[mi]) {
		return search(a, mi + 1, hi, k);
	} else {
		return mi;
	}
}

递归二分查找的递归式：

$T_{n}=\begin{cases}\Theta(1)& \text{若}n = 1 \\T(n/2)+\Theta(1)& \text{若}n > 1\end{cases}$Tn​={Θ(1)T(n/2)+Θ(1)​若n=1若n>1​

求解该递归式：
$\begin{aligned} T(n)= &T(n/2) + 1\\ = &T(n/4) + 2\\ = &T(n/8) + 3\\ = &... ...\\ = &T(n/2^k) + k \end{aligned}$T(n)=====​T(n/2)+1T(n/4)+2T(n/8)+3......T(n/2k)+k​
当$k = log_2n$k=log2​n时，$T(n) = T(1) + log_2n$T(n)=T(1)+log2​n，所以二分查找的时间复杂度为$\Theta(lgn)$Θ(lgn)。

答：不行，虽然本来需要$\Theta(n)$Θ(n)时间去发现元素在已排序的子数组中的位置，使用二分查找可以把该时间缩短至$\Theta(lgn)$Θ(lgn)，但是元素移动需要的时间是不变的，也就是$\Theta(n)$Θ(n)，所以时间复杂度依旧为$\Theta(n^2)$Θ(n2)。

答：先使用$\Theta(nlog_2n)$Θ(nlog2​n)的排序算法对集合进行排序，这需要$\Theta(nlog_2n)$Θ(nlog2​n)的时间。然后循环排序后的集合，在迭代中使用$x$x减去当前循环的数得到$y$y，然后使用二分查找在剩下的元素中查找y，如若找到则S中存在两个其和为x的元素，如若找不到，则进行下个迭代，直到循环结束，则S中不存在两个其和为x的元素。二分查找需要$\Theta(log_2n)$Θ(log2​n)，进行$n$n次循环需要$\Theta(nlog_2n)$Θ(nlog2​n)的时间，所以总时间是要$\Theta(nlog_2n)$Θ(nlog2​n)。