算法设计基础与分析

绪论

什么是算法

一系列解决问题的明确指令，对于符合一定规范的输入，能够在有限的时间内获得要求的输出。

例子：最大公约数：俩个不全为0 的非负整数$m$和$n$的最大公约数记为$gcd(m,n)$​,代表能够整除（即余数为0）$m$ 和$n$的最大正整数。

欧几里得算法

$gcd(m,n)=gcd(n, m \ mod \ n)(m \ mod \ n 表示m除以n 之后的余数)$​​​

$until\ m \ mod\ n = 0$​​ 其中 $gcd(m, 0) = m$

证明：$m$​ , $n$​, 其中 $m > n$​​

则 $m = n*k+r \ , \ r = m \ mod \ n, k是整数$​​​​​

假设存在$u$​​.使得$m = su, n = tu$​​ , $u$​​ 为$m$​​,$n$​​的约数

则$r = su - k(tu) = (s-kt)*u$​，

$m$​ 和 $n$​ 的约数也整除它们的余数$r$​​​

所以$m$​ 和 $n$​ 的任一约数同时也是$n$​和$r$​​ 的约数

反之，$n$和$r$ 的任一约数也是$m$ 和 $n$​​​ 的约数。

// Euclid(m,n)
while(n != 0){
  r = m / n;
  m = n;
  n = r;
}
return m;

连续值检测算法

选取俩者的最小值，向下连续检测数值

局限：当$m$, $n$​中输入为0时，结果是错误的。

t = min(m, n);
while(t > 0）{
 	if(m % t == 0 && n % t == 0){
		return t;
	} else{
    t--;
  }
}

质因数相乘法

找出俩者公共的质因数，相乘得到结果

总结：对比三种计算最大公约数的方法，连续值检测法未能清晰规定算法输入的值域，当输入为0时，计算结果出错；质因数相乘法，对于如果计算质因数未能明确给定计算步骤。算法，应当清晰定义输入输出的值域，清晰定义计算的步骤。

例子：用来阐述一个不大于给定整数$n$的连续质数序列

埃拉托色尼筛选法

1. 初始化 $2$ ​~$n$​​ 的连续整数序列作为候选质数
2. 第一次循环，消去$2$​的倍数（不包括2）
3. 第二次循环，消去$3$的倍数（不包括3）
4. 第三次循环，消去$5$的倍数（不包括5），4之前已经被消去了
5. …$until \ n$​

/** Sievea(n)
 * 连续质数序列产生算法
 * Input:正整数n>1
 * Output:包含所有小于等于n的质数的数组L
 */
public static List<Integer> Sieve(int n){
	int[] A = new int[n+1];
	for(int p = 2; p <= n; ++p){
		A[p] = p;
	}

	for(int p = 2; p <= Math.sqrt(n); ++p){
		if(A[p] != 0){
			int j = p * p;
			while(j <= n){
				A[j] = 0;
				j += p;
			}
		}
	}
	List<Integer> L = new ArrayList<>();
	for(int p = 2; p < n+1; ++p){
		if(A[p] != 0){
			L.add(A[p]);
		}
	}
	return L;
}

当我们正在消去p的倍数，第一个值得考虑的是$p*p$ ，因其他更小的倍数$2p, \cdots ,(p-1)p$已经在之前的步骤中从序列中消去了，所以$pp <= n$， 因此$p <= sqrt(n)$​​

算法问题求解基础

算法是问题程序化解决方案

1. 理解问题：输入输出范围、特殊情况考虑（边界条件等）

2. 确定：

   （1）计算方法（了解设备性能，并行/串行）

   （2）精确或近似解法

   （3）算法设计技术

3. 设计算法：确定合适的数据结构，伪代码描述，流程图

4. 正确性证明

5. 分析算法：简单（易读，易懂），一般（问题的一般性，接受输入的一般性），时间、空间

6. 根据算法写代码

算法效率分析基础

效率分析框架

1. 算法的时间效率和空间效率都用输入规模的函数进行度量
2. 算法基本操作的执行次数来度量算法的时间效率；通过计算算法消耗的额外存储单元的数量来度量空间效率
3. 输入规模相同的情况下，部分算法的效率会有显著差异，需要区分最差效率，平均效率，最优效率
4. 当算法的输入规模趋向于无限大时，它的运行时间（消耗的额外空间）函数的增长次数

渐近符号和基本效率类型

效率分析框架主要关心一个算法的基本操作次数的增长次数，并把它作为算法效率的主要指标，主要用三种渐进符号表示

1. $O(g(n))$:增长次数小于等于$g(n)$​(及其常数倍，$n$​趋向于无穷大)的函数集合
2. $\Omega(n)$:代表增长次数大于等于$g(n)$(及其常数倍，$n$趋向于无穷大)的函数集合
3. $\Theta(n)$：增长次数等于$g(n)$(及其常数倍，$n$趋向于无穷大)的函数集合

利用极限比较增长次数

基本的效率类型

类型	名称	注释
$1$	常量	为数很少的效率最高的算法，很难举出几个合适的例子，因为典型情况下，当输入的规模变得无穷大时，算法的运行时间也会趋向于无穷大
$log \ n$​	对数	一般来说，算法的每一次循环都消去问题规模的一个常数因子，注意，一个对数算法不可能关注它的输入的每一个部分（哪怕是输入的一个固定部分）：对任何能做到这一点的算法最起码拥有线性运行时间
$n$	线性	扫描规模为$n$的列表（顺序查找）的算法属于这个类型
$n \ log \ n$​	线性对数	许多分治算法，包括合并排序和快速排序的平均效率，都属于这个类型
$n^2$	平方	一般来说，这是包含两重嵌套循环的算法的典型效率。线性代数中一些著名的算法属于这一类型
$n^3$	立方	一般来说，这是包含三重嵌套循环的算法的典型效率。线性代数中一些著名的算法属于这一类型
$2^n$	指数	求$n$个元素集合的所有子集是这种类型的典型例子，“指数”这个术语常常被用在一个更广的层面上，不仅包括这种类型，还包括那些增长速度更快的类型
$n!$	阶乘	求$n$个元素集合的完全排列的算法是这种类型的典型例子

非递归算法的数学分析

例1：从$n$​个元素的列表中查找元素最大值的问题

MaxElement(A[0...n-1])
// 求给定数组中的最大元素的值
// 输入：实数数组A[0..n-1]
// 输出：A中最大元素的值
maxVal = A[0]
for(int i = 1; i < n; ++i){
  if(A[i] > maxVal){
    maxVal = A[i];
  }
}
return maxVal;

分析非递归算法时间效率的通用方案

1. 决定用哪个（哪些）参数表示输入规模
2. 找出算法的基本操作（作为一个规律，总是位于算法的最内层循环）
3. 检查基本操作的执行次数是否之依赖于输入规模，如果还依赖于一些其他的特性，则最差效率，平均效率以及最优效率（如有必要）需要分析研究。
4. 建立一个算法的基本操作执行次数的求和表达式
5. 利用求和运算的标准共识和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数

例2: 元素唯一性问题，验证给定数组的$n$个元素是否全部唯一

UniqueElements(A[0,,n-1])
//验证给定数组中的元素是否全部唯一
//输入：数组A[0,,n-1]
//输出：如果A中的元素全部唯一，返回true
//     否则，返回false
for(int i = 0; i < n-1; i++){
  for(int j = i + 1; j < n-1; j++){
    if(A[i] == A[j]){
      return false;
    }
  }
}
return true;

例3:矩阵乘积计算问题 $C=AB$​

// MatrixMultiplication(A[0..n-1,0..n-1],B[0..n-1,0..n-1])
// 用基于定义的算法计算俩个n阶矩阵的乘积
// 输入：两个n阶矩阵A，B
// 输出：矩阵C=ABx
for(int i = 0; i < n; i++){
	for(j = 0; j < n; j++){
		C[i,j]=0;
		for(int k = 0; k < n; k++){
			C[i,j] = C[i,j]+A[i,k]+B[k,j];
		}
	}
}
return C;

例4: 十进制正整数在二进制表示中的数字个数

// Binary(n)
// 输入：十进制正整数n
// 输出：n在二进制表示中的二进制数字个数
count = 1；
while(n > 1){
	count += 1;
	n = Math.floor(n/2);//向下取整
}
return count;

递归算法的数学分析

例1:计算 $n!$

// F(n) = n!
// 递归计算n!
// 输入：非负整数n
// 输出：n!的值
if(n == 0){
  return 1;
}else{
  return F(n-1)*n;
}

当$n > 0$, $F(n)=F(n-1)+1$

$M(n)$表示乘法的执行次数，则$M(n) = M(n-1)+1$

$M(0) = 0$

$M(n)=M(n-1)+1=…=M(n-i)+i=…=M(n-n)+n=n$

分析递归算法时间效率的通用方案

1. 决定用哪个（哪些）参数作为输入规模的度量标准
2. 找出算法的基本操作
3. 检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同。如果有这个可能，则必须对最差效率，平均效率以及最优效率做单独研究
4. 对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件
5. 解这个递推式，或者至少确定它的解的增长次数

例2: 汉诺塔游戏

$M(n)=M(n-1)+1+M(n-1)=2M(n-1)+1$

$M(1)=1$

$M(n)=2[2M(n-2)+1]+1=2^2M(n-2)+1$​

…

$M(n)=2^{n-1}M(n-(n-1))+2^{n-1}+1$

$M(n)=2^n-1$

计算斐波那契数列讨论

$F(n)=F(n-1)+F(n-2)$

$F(0)=0,F(1)=1$

算法的经验分析

对算法效率做经验分析的通用方案

1. 了解实验的目的
2. 决定用来度量效率的度量标准M和度量单位（用操作次数还是直接用时间）
3. 决定输入样本的特性（它的范围和大小等）
4. 为实验准备算法（或若干算法）的程序实现
5. 生成输入样本
6. 对输入样本运行算法（或若干算法），并记录观察到的实验数据
7. 分析获得的实验数据

蛮力法

选择排序和冒泡排序

选择排序

选择出当前元素应该放置的元素（升序排列，找出当前轮次的最小元素），依次循环

$\Theta(n^2)$

SelectionSort(A[0],,A[n-1])
// 该算法用选择排序对给定的数组排序
// 输入：一个可排序的数组A[0..n-1]
// 输出：升序排列的数组A[0..n-1]
for(int i = 0; i < n-1; ++i){
	int minPos = i;
	for(int j = i+1; j < n; ++j){
		if(A[minPos] > A[j]){
			minPos = j;
		}
		swap(A[i], A[minPos]);
	}
}

冒泡排序

比较相邻元素

BubbleSort(A[0..n-1])
// 该算法用冒泡排序对数组A[0.n-1]进行排序
// 输入：一个可排序数组A[0..n-1]
// 输出：非降序排列的数组A[0..n-1]
for(int i = 0; i < n-1; ++i){
	for(int j = 0; j < n-1-i; ++j){
		if(A[j] > A[j+1]){
			swap(A[j], A[j+1]);
		}
	}
}

顺序查找和蛮力字符串匹配

顺序查找

SequentialSearch(A[0..n],K)
// 顺序查找的算法实现。它用了查找键来作限位器
// 输入：一个n个元素的数组A和一个查找键K
// 输出：第一个值等于K的元素的位置，如果找不到这样的元素，返回-1
A[n] = K；
i = 0；
while(A[i] != K){
	i++;
}
if(i < n)
	return i;
else
	return -1;

如果查找序列是有序的话，可以查找到或者大于查找键后直接返回

蛮力字符串匹配

给定一个$n$​个字符串组成的串[称为文本(text)],一个$m(m<=n)$个字符的串[称为模式(pattern)]，从文本中寻找匹配模式的子串。

BrureForeStringMatch(T[0..n-1],P[0..m-1])
// 该算法实现了蛮力字符串匹配
// 输入：一个n个字符的数组T[0..n-1],代表一段文本
// 			一个m个字符的数组P[0..m-1],代表一个模式
// 输出：如果查找成功，返回文本的第一个匹配子串中第一个字符的位置，否则返回-1
for(int i = 0; i < n-m+1; ){
	j = 0;
	while(j < m && P[j] = T[i+j]){
		j++;
		if(j == m){
			return i;
		}
	}	
}
return -1;

最坏情况 $O(nm)$​​

最近对和凸包问题的蛮力算法

最近对问题

最近点对问题要求在一个包含$n$个点的集合中，找出距离最近的俩个点。

一个重要的应用是统计学中的聚类分析。对于$n$个数据点的集合，层次聚类分析希望基于某种相似度度量标准将数据点构成的簇按照层次关系组织起来。

（1）对于数值型数据，相似度度量标准的通常采用欧几里得距离；

（2）对于文本和其他非数值型数据，通常采用诸如汉明距离这样的相似度度量标准。

$d(p_i,p_j)=\sqrt {(x_i-x_j)^2+(y_i-y_j)^2}$

BruteForceClosestPoints(p)
// 使用蛮力法求平面中距离最近的俩点
// 输入：一个n（n>=2)个点的列表p,p1=(x1,y1)...pn=(xn,yn)
// 输出：俩个最近点的距离
$d = \infin$
for(int i = 1; i < n; ++i){
	for(j = i+1; j < n+1; ++j){
		d = min(d, sqrt((xi-xj)^2+(yi-yj)^2));//sqrt是平方根函数
	}
}
return d;

基本操作是计算平方根，其实可以转而比较平方本身，而避免平方根计算，算法的基本操作转为求平方，加快内层循环的速度。

凸包问题

凸集合：对于平面上的一个点集合（有限的/无限的），如果以集合中的任意俩点$p$,$q$为端点的线段都属于该集合，我们说这个集合是凸的。

凸包概念：对于平面上$n$个点的集合，它的凸包就是包含所有这些点（或者在内部，或者在边界上）的最小的凸多边形。

凸包：一个点集合$S$的凸包是包含$S$的最小凸集合，（“最小”意指$S$ 的凸包一定是所有包含$S$ 的凸集合的子集）。

定理：任意包含$n>2$个点（不共线的点）的集合S的凸包是以S中的某些点为顶点的凸多边形（如果所有的点都位于一条直线上），多边形退化为一条线段，但它的俩个端点仍然包含在S中。

凸集合中的极点：对于任何以集合中的点为端点的线段来说，它不是这种线段的中点。

单纯形法用于解决现行规划问题，找到极点也就解出了凸包问题。

对于一个$n$个点集合中的俩个点$p_i,p_j$​​​,当且仅当该集合中的其他点都位于穿过这俩点的直线的同一边时，他们的连线是该集合凸包边界的一部分。对每一对点都做一遍检验之后，满足条件的线段构成了凸包的边界。

在坐标平面上穿过俩个点$(x_1,y_1),(x_2,y_2)$的直线有下列方程定义：

$ax+by=c$​

其中

$a=y_2-y_1$

$b = x_1-x_2$

$c=x_1y_2-y_1x_2$

这样直线可以将平面划分为俩个半平面，其中一个半平面的点都满足$ax+by>c$

另一个半平面中的点$ax+by<c$（直线上的点满足$ax+by=c$）。

为检验某些点事都位于直线的同一边，只需把每个点带入$ax+by-c$,检验这个表达式的符号是否相同。

穷举查找

旅行商问题

(Traveling salesman problem, TSP), 要求找出一条$n$ 个给定城市间的最短路径，使我们在回到出发的城市之前，对每个城市都只访问一次。

该问题可以表述为求一个图的最短哈密顿回路。

哈密顿回路：一个对图的每一个顶点都只穿越一次的回路。

可以假设，所有的回路都开始和结束于相同的特定顶点。可以通过生成$n-1$个中间城市的组合来得到所有的旅行线路，计算这些线路的长度，然后求得最短的线路。

背包问题

给定$n$个重量为$w_1,w_2,…w_n$，价值为$v_1,v_2,…v_n$的物品和一个承重为$W$的背包，求这些物品中一个最有价值的子集，并且能够装到背包中。

穷举查找需要考虑给定的$n$个物品集合的所有子集，为了找出可行的子集（也就是说，总重量不超过背包承重能力的子集），要计算出每个子集的总重量，然后找出它们中间价值最大的子集。

分配问题

有$n$个任务需要分配给$n$个人执行，一个任务对应一个人（每个任务只分配给一个人，每个人只分配一个任务），对于每一对$i,j=1,2,…,n$来说，将第$j$个任务分配给第$i$个人的成本是$C[i,j]$。该问题是要找出总成本最小的分配方案。

一般情况下，需要考虑的排列数量是$n!$，对于该问题有一个效率高效得多的算法是匈牙利算法。

深度优先查找和广度优先查找

深度优先查找

可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。（如果有若干个这样的顶点，可以任意选择一个顶点，选择哪一个邻接的未访问的候选顶点主要是由表示图的数据结构决定的）。过程持续直到遇到一个终点，该顶点的所有邻接点都已被访问过，在后退到起始顶点。如果未访问的顶点仍然存在，该算法必须从其中一顶点开始，重复上述过程。

用栈跟踪深度优先查找的操作是比较方便的。

DFS(G)
//  实现给定图的深度优先查找遍历
// 输入：图G=（V，E）
// 输出：图G的顶点，按照DFS遍历第一次访问到的先后次序，用连续的整数标记将V
//      中的每个顶点标记为0，表示“未访问”
count = 0；
for(Vertex v: V){
	if(v.markedCount == 0){
    	dfs(v);
  }
}
dfs(v);
// 递归访问所有和v相接的未被访问的顶点，然后按照全局变量count的值
// 根据遇到他们的先后顺序，给他们赋值相应的数字
count++;
// 标记v访问
v.markedCount = count;
for(Vertex w : V){
  // w是v的邻接点并且未被访问过
  if(w.adjacent(v) && w.markedCount == 0){
		dfs(w);    
  }
}

DFS产生俩种节点的排列顺序，第一次访问顶点（入栈）的次序和顶点称为终点（出栈）的次序。

DFS在访问所有和厨师顶点有路径相连的顶点后结束，可以用于检查一个图的连通性以及连通分量，利用图的DFS森林形式的表示法可以检查图中是否包含回路。

广度优先查找

首先访问所有和初始顶点邻接的点，然后是离它俩条边的所有未访问顶点，以此类推，直到所有与初始顶点同在一个连通分量中的顶点都被访问过了为止。如果仍然存在未被访问的顶点，该算法必须从图中的其他连通分量重的任意顶点重新开始。

使用队列来跟踪广度优先查找操作时比较方便的。

该队列从遍历的初始顶点开始，将该顶点标记为已访问，在每次迭代的时候，该算法找出所有和队头顶点邻接的未访问顶点，将它们标记为已访问，再把他们入队，然后将队头顶点从队列中移去。

BFS(G)
// 实现给定图的广度优先遍历
// 输入：图G=（V，E）
// 输出：图G的顶点，按照BFS遍历访问到的先后次序，用连续的整数标记
//      将V中的每个顶点标记为0，表示还“未访问”
count = 0；
for(Vertex v: V){
  if(v.markerdCount == 0){
    bfs(v);
  }
}
bfs(v);
//访问所有和v连接的未访问顶点，然后按照全局变量count的值
//根据访问他们的先后次序，给它们赋上相应的数字
count++;
v.markedCount = count;
while(!queue.isEmpty()){
  for(Vertex w : V){
    if(w.adjacent(v) && w.markedCount == 0){
      count++;
      w.markedCount = count;
      queue.push(w);
    }
  }
  queue.pop(w);
}

BFS 只产生顶点的一种排序，因为队列时先进先出的结构，所以顶点入队和出队次序一致。

BFS检查图的连通性和无环性，可以求俩个顶点间边的数量最少的路径。

减治法

利用来一个问题给定实例的解和同样问题较小实例的解之间的某种关系，一旦建立了这种关系，我们既可以从顶向下也可以由底向上来运用该关系。

3种主要变化形式

• 减去一个常量
• 减去一个常量因子
• 减去的规模是可变的

减一技术：规模为$n$​的问题—>规模为$n-1$​的问题—>子问题的解—>原问题的解

减半技术：规模为$n$​的问题—>规模为$n/2$​​的问题—>子问题的解—>原问题的解

减可变规模：计算最大公约数的欧几里得算法$gcd(m,n)=gcd(n,m\ mode\ n)$​

减一技术

插入排序

数组$A[0..n-1]$

遵循减一的思路，假设数组$A[0…n-2]$​​已经有序，$A[0]\le … \le A[n-2]$​​​

则对于$A[n-1]$,我们需要做的就是在这些有序的元素中为$A[n-1]$找到合适的位置，插入进去。

一般来说，可以从左至右扫描该有序数组的子数组，直到遇到一个小于等于$A[n-1]$的元素，然后把$A[n-1]$​插在这个元素的后面，这种被称为直接插入排序。

InsertionSort(A[0..n-1])
// 用插入排序对给定数组排序
// 输入：n个可排序数组构成的一个数组A[0..n-1]
// 输出：非降序排列的数组A[0..n-1]
for(int i = 1; i < n; ++i){
	val = A[i]
	j = i-1;
	while(j >= 0 && A[j] > val){
		A[j+1] = A[j];
		j--;
	}
	A[j+1] = val;
}

拓扑排序

有向图：一个对所有边都指定方向的图

邻接矩阵和邻接链表是俩种表示有向图的主要手段。

当采用这这俩种方式表示时，无向图和有向图只有俩个显著的差异：

（1）有向图的邻接矩阵并不一定表现出对称性

（2）有向图的一条边在图的邻接链表中只有一个相应的节点（不是俩个）

有向图的遍历，深度优先和广度优先查找是主要的遍历算法

在对图的边引入方向后，讨论一个问题，

例如：

一个必修课集合${}$${C_1,C_2,C_3,C_4,C_5}$​学生必须在某个阶段修完这几门课程，可以按照任何次序学习这些课程，只要满足下列条件：

（1） $C_1$​和$C_2$​没有任何先决条件

（2）修完$C_1$​，$C_2$​才能修$C_3$​

（3）修完$C_3$​才能修$C_4$​

（4）修完$C_3$​和$C_4$​才能修$C_5$​​

（5）每个学习只能修一门课程

是否可以按照这种次序列出它的顶点，使得对于图中每一条边来说，边的起始顶点总是排在边的结束顶点之前（是不是能够求出该图节点的这样一个序列？）这个问题称为拓扑排序

如果有向图具有一个有向的回路，该问题无解，为使得拓扑排序成为可能，充要条件是问题中的图必须是一个无环有向图。

有俩种高效的算法是既可以验证是否是无环有向图，又可以在是的情况下输出拓扑排序的一个顶点序列。

第一种：深度优先查找的一个简单应用（DFS）：执行一次DFS遍历，并记住顶点变成死端（即推出遍历栈）的顺序。

将该次序反过来就得到拓扑排序的一个解，当然，在遍历的时候不能遇到回边。

如果遇到一条回边，该图就不是无环有向图，并且对它的顶点的拓扑排序是不可能的。

当一个顶点$v$退出DFS栈时，在比$v$更早退出栈的顶点中，不可能存在顶点$u$拥有一条从$u$到$v$的边（否则，$(u,v)$会成为一条回边），所以，在退栈的队列中，任何这样的顶点$u$都会排在$v$的后面，并且在逆序队列中会排在$v$的前面。

第二种：基于减一技术的一个直接实现（源删除算法）：不断地做这样一件事，在余下的有向图中求出一个源（source），它是一个没有输入边的顶点，然后把它和从它出发的边都删除，（如果有多个这样的源，可以任意选择一个。如果这样的源不存在，算法停止，因为该问题无解）顶点被删除的次序就是拓扑排序问题的一个解。

拓扑排序在计算机科学中有很多应用，包括程序编译中的指令调度，电子表格单元格的公式求值顺序以及解决链接器中的符号依赖问题。

生成组合对象的算法

组合对象中最重要的类型就是排列，组合，给定集合的子集。离散数学有一个分支名为组合数学，专门研究组合对象。我们这里感兴趣的主要是如何生成它们。

生成排列

假如需要对元素进行排列的集合是从$1$到$n$的简单整数集合，解释为$n$个元素${a_1，..a_n}$​的元素下标。

对于生成${1,…n}$的所有$n!$个排列的问题：

减一技术：将问题规模减一，转化成$(n-1)!$​​个排列，把$n$插入$n-1$个元素的每一种排列中的$n$个可能位置中去，来得到较大规模问题的一个解。

Johnson Trotter(n)
// 实现用来生成排列的Johnson Trotter算法
// 输入：一个正整数n
// 输出： {1,...,n}的所有排列的列表
将第一个排列初始化为12..n
while(存在一个移动元素){
   求最大的移动元素k
   把k和它箭头指向的相邻元素互换
   调转所有大雨k的元素的方向
   将新排列添加到列表中
}

对于$n=3$，字典序：

$123, 132，213，231，312，321$

LexicograhicPermute(n)
// 以字典序产生排列
// 输入：一个正整数n
// 输出：在字典序下{1,..,n}所有排列的列表
init(第一个排列为12..n)
while(最后一个排列有俩个连续升序的元素){
  找出使得a_i<a_i+1的最大的i（a_i+1>a_i+2>..>a_n）
 
  找到使得a_i<a_j的最大索引j(j>=i+1)因为a_i < a_i+1
  // 交换a_i，a_j
  swap(a_i,a_j);
  // 将a_i+1到a_n反序
  reverse(a,i+1,n);
  // 将这个新排列添加到列表中
  resultList.add(a);
}

生成子集

幂集：一个集合的所有子集的集合称为它的幂集。

是否存在一种生成位串的最小变化算法，使得每一个位串和它直接前趋之间仅仅相差一位（就子集来说，我们希望每一个子集和它的直接前趋之间的区别，要么是增加一个元素，要么是删除一个元素，但俩者不能同时发生）

》〉》〉》 二进制反射格雷码（binary reflected Gray code）

例如$n=3$,

$000 \ 001 \ 011\ 010\ 110\ 111\ 101\ 100$

BRGC(n)
// 递归生成n位的二进制反射格雷码
// 输入：一个正整数n
// 输出：所有长度为n的格雷码位串列表
if(n==1){
  表L包含位串0和位串1
}else{
  // 生成长度为n-1的位串列表L1
 	L1 = BRGC(n-1)
  // 把表L1倒序后复制给L2
  copy(reverse(L1), L2)
  // 把0加到表L1中的每个位串前面
  L1.addFront(0)
  // 把1加到表L2中的每个位串前面
  L2.addFront(1)
  // 把表L2添加到表L1后面得到表L
  L = L1.addTail(L2)
}
return L;

减常因子算法

减常因子算法常常具有对数时间效率，非常高效，因此实例并不多。

折半查找

对于有序数组来说，折半查找是一种性能卓越的算法，它通过逼阿胶查找键K和数组中间元素$A[m]$来完成查找工作，如果它们相等，算法结束。否则，如果$K<A[m]$​，就对数组的前半部分执行该操作，如果$K>A[m]$,则对数组的后半部分执行该操作。

折半查找是基于递归的思想，也可以非递归算法实现。

BinarySearch(A[0..n-1],K)
// 实现非递归的折半查找
// 输入：一个升序数组A[0..n-1]和一个查找键K
// 输出：一个数组元素的下标，该元素等于K；如果没有这样一个元素，返回-1
l = 0, r = n-1;
while(l <= r){
  int m = (l+r)/2
  if(K == A[m]) return m;
  else if(K < A[m]) r = m-1;
  else if(K > A[m]) l = m+1;
}
return -1;

$C_{avg} \ = \log_2n$​​

假币问题

在$n$枚外观相同的硬币中，有一枚假币。

在一架天平上，可以比较任意俩组硬币，可以通过观察天平向右倾还是向左倾还是水平，判断俩组硬币重量是否相同，或者哪一组更重，要求设计一个高效的算法来检测出这枚假币。

假设假币相对真币较轻

最自然的思路是将$n$枚硬币分为俩摊，每堆有$n/2$枚硬币

（1）如果$n$​​为奇数，就留下一枚额外的硬币，然后把俩堆硬币放在天平上，如果俩堆硬币重量相同，那么放在旁边的即为假币；否则循环比较较轻的一堆硬币

（2）如果$n$​为偶数，则循环比较较轻的一堆硬币

$W(n)=W(n/2)+1,当n>1，W(1)=0$

$W(n)=log_2n$

这并不是最高效的解法，如果把硬币分为三堆呢？每堆$n/3$枚硬币，将会更好

$W(n)=log_3n$

俄式乘法

假设$n$和$m$​是俩个真整数，需要计算它们的乘积。

同时，我们用$n$​的值作为实例规模的度量标准，这样，

（1）如果$n$​是偶数，一个规模为原来一半的实例必须要对$n/2$​进行处理，对于该问题较大的实例的解和较小实例的解的关系，有一个显而易见的公式：

$nm=n2m/2$​

（2）如果$n$是奇数，只需要对该公式做轻微调整：

$nm=(n-1)/22m+m$

通过应用这个公式，并以$1*m=m$作为算法停止的条件。

既可以采用递归也可以采用迭代计算，该算法只包括折半，加倍，相加这几个操作，硬件实现速度也很快，使用移位即可完成折半和加倍操作

约瑟夫斯问题

$n$个人围成一个圈，并将他们从$1$到$n$​​编上号码。从编号为$1$的那个人那里开始这个残酷的计数，每次消去第二个人直到只留下最后一个幸存者。

要求算出幸存者的号码$J(n)$​

（1）如果$n$为偶数，$n=2k$，对整个圆圈处理第一遍之后，生成了同样问题的规模减半的实例。唯一差别是位置的编号。

例如一个初始位置为$3$​的人在第$2$​轮会处于$2$​号位置上，初始位置$5$​的人会处在$3$​号位置上，以此类推，

$J(2k)=2J(k)-1$​​

（2）如果$n$​为奇数，$n=2k+1$​。第一轮消去所有偶数位置上的人，如果把紧接着消去的位置 $1$​上的人也加进来，留下一个规模为$k$​的实例。这里，为了得到与新的位置编号相对应的初始位置编号，我们必须把新的位置编号乘$2$​再加上$1$​,因此对于奇数$n$​,

$J(2k+1)=2J(k)+1$

由于这个游戏可以看成一个环形，位置的变化是一种环形内位置的移位过程，我们可以对$n$本身做一次向左的循环移位来得到$J(n)$，

$J(6)=J(110_2)=101_2=5$

$J(7)=J(111_2)=111_2=7$​

减可变规模算法

在减治法的第三个主要变化形式中，算法在每次迭代时，规模减小的模式和另一次迭代时不同的，计算最大公约数的欧几里得算法提供了这类算法的一个非常好的例子。

计算中值和选择问题

选择问题是求一个$n$个数列表的第$k$个最小元素的问题。

这个数字被称为第$k$​个顺序统计量

对于$k=1,k=n$，可以扫描元素列表，获取最小或最大元素。

该问题的一个有意思的情况是在$k=n/2$​​时，要求找出这样一个元素，列表中的一半元素哒，又比一半元素小。这个元素称为中值。

（1）一种方法是先将列表排序，选出第$k$个元素。算法的运行时间取决于排序算法的效率，选用类似合并排序的算法，效率是$O(nlog_n)$​

当然，整个列表的排序可能没有必要，毕竟我们只是找出第$k$小的元素

（2）划分的思路。将一个给定列表根据某个值$p$（例如列表的第一个元素）进行划分，对列表元素进行重新整理，使左边部分包含所有小于等于$p$的元素，紧接着是中轴本身，右边是所有大于或等于$p$的元素

又俩种主要的划分算法，$Lomuto划分$，$Hoare算法$​

$|所有小于等于p的元素|$ $|p|$ $|所有大于或等于p的元素|$​

这里讨论$Lomuto划分$

// LomutoPartition(A[l,,r])
// 采用Lomuto算法，用第一个元素作为中轴子对数组进行划分
// 输入：数组A[0..n-1]的一个子数组A[l..r],它由左右俩边的索引l和r(l<=r)定义
// 输出：A[l..r]的划分和中轴的新位置
p = A[l]
s = l
for(int i = l+1; i <= r; i++){
	if(A[i] < p){
		s = s+1;
    swap(A[s],A[i]);
	}
}
swap(A[l],A[s]);
return s;

如何利用划分列表来寻找第$k$最小元素呢？

快速选择：假设列表时以数组实现的，其元素索引从$0$开始，而$s$是划分的分割位置，也就是划分后中轴所在元素的索引。

（1）如果$s=k-1$，中轴$p$即为第$k$小的元素

（2）如果$s>k-1$​，第$k$​小元素就是被划分数组左边部分的第$k$​​小元素

（3）如果$s<k-1$​,第$k$​小元素就是被划分数组右边部分的第$(k-s)$​​​小元素　

递归

// Quickselect(A[l..r],k)
// 用基于划分的递归算法解决选择问题
// 输入：可排序的数组A[0..n-1]的子数组A[l..r]和整数k(1<=k<=r-l+1)
// 输出：A[0..n-1]中第k小元素的值
s = LomutoPartition(A[l,,r]) // 或者另一个划分算法
if s == l+k-1 return A[s]
else if s > l+k-1 Quickslect(A[l,,s-1], k)
else Quickselect(A[s+1,,r], l+k-1-s)

非递归

如果是求取第$k$大元素，类似

效率分析：$O(n^2)$

插值查找

作为减可变规模算法的下一个例子，我们考虑一个查找有序数组的算法，插值查找

不同于折半查找总是查找键和给定有序数组的中间元素进行比较（也因此把问题规模消减了一半），插值查找为了找到用来和查找键进行比较的数组，考虑了查找键的值。

二叉树的查找和插入

二叉查找树：这种二叉查找树的节点包含了可排序项集合中的元素，每个节点一个元素，并使得对于每个节点来说，所有左子树的元素都小于子数根节点的元素，所有右子树的元素都大于子树根节点的元素。

当在这样一棵树中查找给定值$v$的元素时，可以递归采用下面的方法。

（1）如果这棵树为空，则查找失败；

（2）如果这棵树不为空，把$v$和根节点$K$​作比较，

• 如果等于$K$，查找结束​
• 如果比$K$​​小，继续在左子树中查找
• 如果比$K$​​​大。继续在右子树中查找

一棵查找树的规模的最佳度量标准就是树的高度，树的高度的减少通常都不相同，这给我们一个很好的减可变规模算法的例子。

查找效率最差是当二叉查找树只有一边时，效率为$\Theta(n)$​,平均查找效率为$\Theta(logn)$​

拈游戏

一般来说，该游戏中会有若干堆棋子，但我们先来考单堆棋子的版本。

现在只有一堆$n$个棋子。

俩个玩家轮流从堆中拿走最少一个，最多$m$​个棋子。每次拿走的棋子数都可以不同，但能够拿走的上下限数量不变。如果每个玩家都做出了选择，哪个玩家能够胜利拿到最后那个棋子？是先走的还是后走的？

当且仅当$n \mod\ (m+1) \neq 0$​​​，胜局

因此，胜利的策略是每次拿走$n \mod\ (m+1)$​个棋子，如果背离这个策略，则会把胜局留给对手

一般来说，拈游戏包含$I>1$堆棋子，每堆的棋子数分别$n_1,n_2,…n_I$​。每次走的时候，玩家可以从任意一堆棋子中拿走任意允许数量的棋子，甚至可以把一堆都拿光。游戏的目的同样是成为最后一个还能走的玩家。

这种形式的拈游戏的解出人意料，竟然基于堆中棋子数的二进制表示。$b_1,b_2,..b_I$​分别表示各堆棋子数的二进制表示。计算它们的二进制数位和，也称为拈和，即对每一位分别求和并忽略进位。

可以证实，当且仅当二进制数位和中包含至少一个$1$​时，该实例是一个胜局，只包含$0$​时是一个败局。

例如：$n_1=3,n_2=4,n_3=5$​,数位和（拈和）:011+100+101=010。该实例对于先走的玩家来说是一个胜局，要找到该局的一个胜手，玩家需要改变三个位串在中的一个，使得新的二进制数位和仅包含$0$​。因此，先手玩家从第一堆中拿走$2$​个棋子。

分治法

分治法是按照一下方案工作的：

1. 将一个问题划分为同一类型的若干子问题，子问题最好规模相同。
2. 对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）
3. 有必要的话，合并这些子问题的解，已得到原始问题的答案。

分治法对于并行计算时非常理想的，因为各个子问题都可以由各自的CPU同时计算。

合并排序

合并排序是成功应用分治技术的一个完美例子。

对一个需要排序的数组$A[0..n-1]$ ，合并排序把它一分为二：$A[0..\lfloor n/2\rfloor-1]$和$A[\lfloor n/2\rfloor..n-1]$。并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。

// MergeSort(A[0..n-1])
// 递归调用mergersort来对数组A[0..n-1]排序
// 输入：一个可排序的数组A[0..n-1]
// 输出：非降序排列数组A[0..n-1]
if(n>1){
	copy A[0..[n/2]-1] to B[0..[n/2]-1]
	copy A[[n/2]-1..n-1] to C[0..[n/2]-1]
	MergeSort(B[0..[n/2]-1])
	MergeSort(C[0..[n/2]-1])
	// Merge()见下文
	Merge(B,C,A)
}

对俩个有序数组的合并，可以通过下面的算法完成。

初始状态下，俩个指针（数组下标）分别指向俩个带合并数组的第一个元素。

然后比较这俩个元素的大小，将较小的元素添加到一个新创建的数组中。

接着，被复制数组的指针后移，指向较小元素的后继元素。

上述操作，一直持续到两个数组中的一个被处理完为止。

最后，在未处理完的数组中，剩下的元素被复制到新数组的尾部。

// Merge(B[0..p-1],C[0..q-1],A[0..p+q-1)
// 将俩个有序数组合并为一个有序数组
// 输入：俩个有序数组B[0..p-1],C[0..q-1]
// 输出：A[0..p+q-1]中已经有序存放了B和C中的元素
i = 0, j = 0, k = 0;
while(i < p && j < q){
	if(B[i] <= C[j]){
		A[k] = B[i];
		i++;
	}else{
		A[k] = C[j];
		j++;
	}
	k++;
}
if(i == p){
	copy C[j..q-1] to A[k..p+q-1]
}else{
	copy B[i..p-1] to A[k..p+q-1]
}

合并排序算法的效率，简单起见，假设$n$是$2$的乘方

键值比较次数$C(n)$的递归关系式为：

当$n>1$,$C(n)=2C(n/2)+C_{merge}(n),C(1)=0$

$C_{merge}(n)$即合并阶段进行键值比较的次数。每做一步都需要进行一次比较，比较之后，俩个数组中尚需处理的元素总个数减$1$。在最坏情况下，无论那个数组都不会为空，除非另一个数组只剩下最后一个元素（举例来说，最小的元素轮流来自于不同的数组）。因此，对于最坏情况来说，$C_{merge}(n)=n-1$,有以下递推式：当$n>1$,$C_{worst}(n)=2C_{worst}(n/2)+(n-1),C_{worst}(1)=0$

$C_{worst}(n)=nlog_2n-n+1$,效率属于$\Theta(nlogn)$。

合并排序的显著优点在于其稳定性，主要缺点是该算法需要线性的额外空间。主要有俩类变化形式。

首先，算法可以自底向上合并数组的一个个元素对，然后再合并这些有序对，以此类推，这就避免了使用堆栈处理递归调用时的时间和空间开销。

其次，可以吧数组划分为待排序的多个部分，再对它们递归排序，最后将其合并在一起。这个方案尤其适合在对存放在二级存储空间的文件进行排序。也被称为多路合并排序。

快速排序

快速排序是另一种基于分治技术的重要排序算法。不像合并排序是按照元素在数组中的位置对他们进行划分，快速排序按照元素的值对它们进行划分。

建立了一个划分之后，$A[s]$已经位于它在有序数组中的最终位置，接下来我们可以继续对$A[s]$前和$A[s]$后的子数组分别进行排序。

快排与合并排序的不同之处在于：在合并排序算法中，将问题划分成俩个子问题是很快的，算法的主要工作在于合并子问题的解，而在快速排序中，算法的主要工作在于划分阶段，而不需要再去合并子问题的解。

// Quicksort(A[l..r])
// 用Quicksort对子数组排序
// 输入：数组A[0..n-1]中的子数组A[l..r],由左右下表l和r定义
// 输出：非降序排列的子数组A[l..r]
if (l < r){
  // s是分裂位置
	s = Partition(A[l..r])
	QuickSort(A[l..s-1])
	QuickSort(A[s+1..r])
}

作为一种划分算法，我们当然可以使用之前讨论的Lomuto划分，也可以使用Hoare划分。Hoare是英国杰出的计算机科学家，快速排序算法的发明者。

与以前一样，我们要选择一个中轴，接下来会根据该元素的值来划分子数组，选择中轴有许多不同的策略，这个选择与算法的效率有关，暂定我们选择子数组中的第一个元素，即$p=A[l]$。

分别从子数组的俩端进行扫描，并且将扫描到的元素与中轴比较，从左到右的扫描（用指针$i$表示）从第二个元素开始，因为我们希望小于中轴的元素位于子数组的左半部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才停止。从右至左的扫描（下面用指针$j$表示）从最后一个元素开始。因为我们希望大于中轴的元素位于子数组的右半部分，扫描会忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止。

俩次扫描全部停止以后取决于扫描的指针是否相交：会发生$3$种不同的情况。

（1）扫描指针$i$和$j$不相交，即$i<j$，$swap(A[i],A[j])，i++,j–$，

（2）扫描指针$i$和$j$相交，即$i==j$，被指向元素的值一定等于$p$

（3）$i>=j$，$swap(A[i],A[j])$。

为啥当遇到与中轴元素相等的元素时值得停止扫描？

因为当遇到有很多相同元素的数组时，这个方法可以将数组分得更加平均，从而使得算法运行得更快。

// HoarePartition(A[l..r])
// 以第一个元素为中轴，对子数组进行划分
// 输入：数组A[0..n-1]中的子数组A[l..r]，由左右下标l和r定义
// 输出：A[l..r]的一个划分，分裂点的位置作为函数的返回值
p = A[l]
i = l;j = r+1
while(i < j){
	while(A[i] < p){
		i++;
	}
	while(A[j] > p){
		j--;
	}
	swap(A[i],A[j]);
}
// 当i>=j撤销后最后一次交换
swap(A[i],A[j]);
swap(A[l],A[j]);
return j;

快速排序时不稳定的，同时还需要一个堆栈来存储那些还没有被排序的子数组的参数。尽管可以通过总是先对较短子数组排序的方法来使堆栈的大小降低到$O(logn)$，但是还是比堆排序$O(1)$的空间效率差。

二叉树遍历及其相关特性

如何把分治技术应用到二叉树中。二叉树定义为若干节点的一个有限集合，它要么为空，要没由一个根和俩棵树称为$T_L$和$T_R$的不相交二叉树构成。这俩棵二叉树分别为根的左右子树。

定义本身把二叉树划分为同样类型的俩个更小的组成部分-左子树和右子树。

作为一个例子，考虑计算二叉树高度的递归算法。

树的高度：从叶子到根之间的最长路径长度。

二叉树的高度计算：它是根的左右子树最大高度加$1$（加$1$代表根所在的那一层），如果把空树的高度定义为$-1$

// Height(T)
// 递归计算二叉树的高度
// 输入：一棵二叉树T
// 输出：T的高度
if T == null return -1;
return max(Height(T_L), Height(T_R))+1;

给定的二叉树的节点数$n(T)$来度量问题实例的规模。为计算俩数中的较大值，算法执行比较次数等于算法执行的加法操作次数$A(n(T))$.对于$A(n(T))$,有如下递推关系：

当$n(T)>0$,$A(n(T))=A(n(T_{left}))+A(n(T_{right}))+1$

$A(0)=0$

在了解这个递推关系之前，先指出，加法运算并不是该算法中最频繁执行的操作，那是哪个操作呢？检查树是否为空，这才是二叉树算法中的典型操作。

对于非空完全为叉树来说，$n$和$x$分别代表父母节点和叶子极点的数量

回到$Height$算法中，检查树是否为空的比较操作次数为：

$C(n)=n+x=2n+1$

而加法操作的次数为：$A(n)=n$

二叉树的三种经典遍历算法

前序遍历：根在访问左右子树之前就被访问

中序遍历：根在访问左子树后，但在访问右子树之前被访问

后序遍历：根在访问左右子树之后被访问

大整数乘法和Strassen矩阵乘法

俩个数的乘法和俩个方阵的乘法，俩个算法都巧妙的运用分治技术获得更好的渐进效率。

大整数乘法

如果我们使用经典的笔算算法来对俩个$n$位整数相乘，第一个数中的$n$个数字都要分别被第二个数中的$n$个数字相乘，这样$n^2$次位乘。虽然看上去设计一个乘法次数小于$n^2$的算法是不可能的，但事实证明并非如此。

举例：$23 \times 14$

$23=2\times10^1+3\times10^0$

$14=1\times10^1+4\times10^0$

$23\times14=(2\times10^1+3\times10^0)\times(1\times10^1+4\times10^0)$

$23\times14=(2\times1)\times10^2+(2\times4+3\times1)+(3\times4)\times10^0=322$

但这和笔算算法一样，都是用来$4$次位乘，由于$2\times1$和$3\times4$是无论如何都需要计算的。可以复用它们的乘积

$2\times4+3\times1=(2+3)\times(1+4)-(2\times1)-(3\times4)$

计算俩个$n$位整数$a$和$b$的积$c$

其中$n$是一个正的偶数。我们从中间把数字一分为二，

把$a$的前半部分记为$a_1$,后半部分记为$a_0$;同理$b$记为$b_1$和$b_0$

$a=a_110^{n/2}+a_0$

$b=b_110^{n/2}+b_0$

$c=a\times b=(a_110^{n/2}+a_0)\times (b_110^{n/2}+b_0)=(a_1\times b_1)10^n+(a_1b_0+a_0\times b_1)10^{n/2}+(a_0\times b_0)=c_210^n+c_110^{n/2}+c_0$

其中$c_2=a_1 \times b_1,c_0=a_0\times b_0, c_1=(a_1+a_0)\times (b_1+b_0)-(c_2+c_0)$

$c_2$是它们前半部分的积，$c_0$是它们后半部分的积，$c_1$是$a$俩部分和与$b$俩部分和的积减去$c_2$与$c_0$的和。

如果$n/2$也是偶数，即可以应用相同的方法计算$c_2$和$c_0$和$c_1$。

因此，如果$n$是$2$的乘方，我们就得到了一个计算俩个$n$位数积的递归算法。当$n==1$时停止。

该算法会做多少次位乘呢？

因为$n$位数的乘法需要对$n/2$位数做三次乘法运算，乘法次数$M(n)$递归式如下：

当$n>1$时，$M(n)=3M(n/2),M(1)=1$

当$n=2^k$时，可以反向替换法对它求解：

$M(2^k)=3M(2^{k-1})=3^iM(2^{k-i})=3^kM(2^{k-k})=3^k$

因为$k=log_2n$，$M(n)=3^{log_2n}=n^{log_23}\approx n^{1.585}$,

$a^{log_bc}=c^{log_ba}$

该算法需要的加法和减法的次数呢？

用$A(n)$代表使用上述算法对俩个$n$位十进制数相乘所需要的加减法运算次数。

除了需要对$n/2$位数之间进行三次相乘操作，即$3A(n/2)$次乘法运算，上面的公式还需要$5$次加运算和$1$次减运算。因此有递推式：

当$n>1$时，$A(n)=3A(n/2)+cn,A(1)=1$

应用本章开头介绍的主定理，得到$A(n)\in \Theta (n^{log_23})$

Strassen矩阵乘法

$\left[
\begin{matrix}
c_{00}&c_{01}\c_{10}&c_{11}
\end{matrix}
\right] = \left[
\begin{matrix}
a_{00}&a_{01}\a_{10}&a_{11}
\end{matrix}
\right] \times \left[\begin{matrix}
b_{00}&b_{01}\b_{10}&b_{11}
\end{matrix}
\right] = \left[
\begin{matrix}
m_1+m_4-m_5+m_7 & m_3+m_5\m_2+m_4 & m_1+m_3-m_2+m_6
\end{matrix}
\right] $

其中：

$m_1 = (a_{00}+a_{11})\times(b_{00}+b_{11})$

$m_2 = (a_{10}+a_{11})\times b_{00}$

$m_3 = a_{00}\times(b_{01}-b_{11})$

$m_4 = a_{11}\times(b_{10}-b_{00})$

$m_5 = (a_{00}+a_{01})\times b_{11}$

$m_6 = (a_{10}-a_{00}) \times (b_{00}+ b_{11})$

$m_7 = (a_{01}-a_{11}) \times (b_{10}+ b_{11})$

分治法解最近对问题和凸包问题

最近对问题

令$P$为笛卡尔平面上$n>1$个点构成的集合，假设集合中的每个点都不一样，且是按照其$x$轴坐标升序排列的。

$Q$为$P$中集合的点，但是按照其$y$轴坐标升序排列的。

求最近点对之间的欧几里得距离

蛮力法

当$2<=n<=3$时，枚举俩个点对，得到最小距离的点对，时间复杂度为$O(n^2)$

分治求解法

当$n>3$时，可以利用点集在$x$轴方向上的中位数$m$，在该处作一条垂线，将点集分成大小为$\lceil n/2 \rceil 和 \lfloor n/2 \rfloor$的俩个子集$P_l$和$P_r$。通过递归求解子问题$P_l$, $P_r$来得到最近点对问题的解。其中$d_l$和$d_r$分别表示在$P_l$和$P_r$中最近对的问题，并定义$d=min(d_l,d_r)$

凸包问题

变治法

本章讨论一组设计方法，基于变换的思想，称为变治法，因为这些方法都是分成俩个阶段工作的。在“变”的阶段，出于这样或者那样的原因，把问题的实例变得更容易求解，然后在第二阶段“治”的阶段，对于实例进行求解。

主要$3$种类型：

实例化简：变换同样问题为一个更简单或更方便的实例

改变表现：变换同样实例的不同表现

问题化简：变换为另一个问题的实例，这种问题的算法时已知的

预排序

对于排序算法有这样一个事实，如果列表时有序的，许多关于列表的问题的更容易求解。为简单起见，假设所有列表都是用数组来实现的。

检查数组中的元素唯一性

蛮力法对数组中的元素对进行比较，直到找到俩个相等的元素，或者所有的元素对都已比较完毕，它的最差效率为$\Theta (n^2)$。

换一种做法，可以预先对数组进行排序，然后只检查它的连续元素。

//PresortElementUniqueness(A[0..n-1]
//先对数组排序来解元素唯一性问题
//输入：n个可排序元素构成一个数组A[0..n-1]
//输出：如果A没有相等元素，返回true,否则返回false
对数组A排序
for(int i = 0; i < n-1; i++){
	if(A[i]==A[i+1]){
  	return false;
  }
}
return true;

$T(n)=T_{sort}(n)+T_{scan}(n)\in\Theta(nlogn)+\Theta(n)=\Theta(nlogn)$

模式计算

在给定的数字列表中最经常出现的一个数值称为模式。

如果用蛮力法对计算模式将会对列表进行扫描，并计算它的所有不同值出现的频率。为实现这个思路，可以在另一个列表中存储已经遇到的值和它们出现的频率。不难发现，该算法的最差输入是一个没有相等元素的列表，对于这样一个列表，它的第$i$个元素和目前唯一数值的辅助列表中$i-1$个元素比较，然后再加入到辅助列表中，并把出现频率设为$1$。因此，在创建频率列表时，该算法的最差比较次数为：

$C(n)=\sum_{i=1}^n=0+1+..+(n-1)=\frac {(n-1)n}2\in\Theta(n^2)$

// PresortMode(A[0..n-1])
// 先对数组排序来计算它的模式
// 输入： 可排序元素构成的数组A[0..n-1]
// 输出： 该数组的模式
i = 0;//当前一轮从为止i开始
modeFrequency = 0;//目前为止求出的最高频率
while(i <= n-1){
	runLength = 1;
	runValue = A[i];
	while(runLength + i <= n-1 && A[i+runLength]==runValue){
		runLength = runLength + 1;
	}
	if(runLength > modeFrequency){
		modeFrequency = runLength;
		modeValue = runValue;
	}
	i += runLength; 
}
return modeValue;

查找问题

考虑$n$个可排序项构成一个给定数组中查找某个给定值$v$的问题。这里的蛮力接发是顺序查找，最坏情况下需要进行$n$此比较。如果该数组是预先排好序的，我们就可以应用折半查找，最坏情况下只需进行$\lfloor log_2n \rfloor +1$

假设使用最搞笑的$nlogn排序$，这个查找算法再最差情况下的总运行时间是

$T(n)=T_{sort}(n)+T_{select}(n)=\Theta(nlogn)+\Theta(logn)=\Theta(nlogn)$

然而这比顺序查找还要差，对于平均效率来说，也是同样的情况，当然如果需要再同一个列表中查找多次，在排序上花费时间应该是值得的。

那么如果使得预排序有意义，至少需要进行多少次查找？

高斯消去法

由俩个线性方程构成的二元联立方程组
$$
{方程组}\begin{cases}a_{11}x+a_{12}y=b_1 \a_{21}x+a_{22}y=b_2 \end{cases}
$$

求解的方法是无论用哪个方程，先把一个变量表示为另一个变量的函数，再把这个结果代入另一个方程中，得到一个线性方程，然后用它的解来求出另一个变量的值。

当需要解一个包含$n$个方程的$n$元联立方程组：
$$
\begin{equation}
\begin{cases}
a_{11}x_{1}+a_{12}x_{2}+…+a_{1n}x_{n}=b_1\
a_{21}x_{1}+a_{22}x_{2}+…+a_{2n}x_{n}=b_2\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\
a_{n1}x_{1}+a_{n2}x_{2}+…+a_{nn}x_{n}=b_n\
\end{cases}
\end{equation}
$$
其中$n$是一个大数，对于俩个联立方程的解法推广到这种方程组上求解显得笨重，高斯消元法：思路是将$n$个线性方程构成的$n$元联立方程组变换为一个等价的方程组（即解和原来的方程组一样），该方程组有着一个上三角的系数矩阵，这种矩阵的主对角线下方元素全部为$0$.

用矩阵的符号可以表示为$$Ax=b \Rightarrow A’x=b’$$

其中

$$A = \left[\begin{array}{} a_{11}&a_{21}& … &a_{n1}\ a_{21}&a_{22}& … &a_{n2} \ \vdots & \vdots & \ddots & \vdots \ a_{n1}&a_{n2}& … &a_{nn} \end{array} \right] $$

$$A’=\left[ \begin{array}{} a’{11}&a’{21}& … &a’{n1}\ 0&a’{22}& … &a’{n2} \ \vdots & \vdots & \ddots & \vdots \ 0&0& … &a’{nn} \end{array} \right]$$

前向消去算法

ForwardElimination(A[1..n,1..n],b[1..n])
//对一个方程组的系数矩阵A应用高斯消去法
//用该方程组右边的值构成的向量b来扩展该矩阵
//输入：矩阵A[1..n,1..n]和列向量b[1..n]
//输出：一个代替A的上三角形等价矩阵图，相应的右边的值位于第(n+1)列中
for(int i = 1; i < n; ++i){
	A[i,n+1] = b[i]
}
for(int i = 1; i < n-1; ++i){
	for(int j = i+1; j < n; ++j){
		for(int k = n+1; k > i; k--){
			A[j,k] = A[j,k] - A[i,k]*A[j,i]/A{i,i]
		}
	}
}

需要注意的俩个事实

1. 并不总是正确的，如果A[i,i]=0，不能作除数；在该算法的第$i$次迭代中不能把$i$作为基点。同时，$A[i,i]$可能非常小，那么$A[j,i]/A[i,i]$很大，以至于$A[j,k]$的新值会因为舍入误差而歪曲，这个误差是在俩个数量级相差非常大的时候相减时发生的。
2. 最内层的循环效率十分低

为了避免问题1，可以每次都去找第$i$列系数的绝对值最大的行，然后把它作为第$i$次迭代的基点。这种修改称为部分选主元法，它能保证比例因子的绝对值永远不会大于1.

优化后的算法

BetterForwardElimination(A[1..n,1..n],b[1..n])
// 用部分选主元法实现高斯消去法
// 输入：矩阵A[1..n,1..n]和列向量b[1..n]
// 输出：一个代替A的上三角形等价矩阵图，相应的右边的值位于第(n+1)列中
for(int i = 1; i < n; ++i){
	A[i,n+1] = b[i]}