线性同余法

线性同余法：产生伪随机数最常用方法

• $d \leq m$：随机序列种子
• $b \geq 0, c \geq 0, m \geq 0$：关系到产生随机序列的随机性能

  • $m$：应该取得充分大
  • $gcd(m ,b)=1$：可以取b为素数

无符号整形二进制

1数量

• 目标：统计 unsinged 二进制表示中 1 数量
• 思路方向
  • 移位遍历
  • 分治统计

仅遍历1

1
2
3
4
5
6
7
8

int population(unsigned int bits){
	int result = 0;
	while (bits != 0){
		bits &= bits - 1;
		++result;
	}
	return result;
}

• 遍历减少：仅仅遍历无符号整形二进制表示中 1 次数
  • bits &= bits - 1 将末尾 1 消除

分治+查表

1
2
3
4
5
6
7
8
9
10
11
12
13

int * initialization(){
	int * table = new int[256];
	for (int i = 1; i < 256; i++){
		table[i] = (i & 0x1) + table[i >> 1];
	}
	return table;
}
int population(int bits, int * table){
	return table[bits & 0xff] +
		table[(bit >> 8) & 0xff] +
		table[(bit >> 16) & 0xff] +
		table[(bit >> 24) & 0xff]
}

• 思路
  • 建表：为 8bits 数建立 256 长度的 1 数量表
    • 递推建立：f(n) = f(n >> 1) + last_bit(n)
  • 分治：将无符号整型分4块查表、加和结果

分治

1
2
3
4
5
6
7
8
9

int population(unsigned int bits){
	// 分组计算
	bits = (bits & 0x55555555) + ((bits >> 1) & 0x55555555);
	bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
	bits = (bits & 0x0f0f0f0f) + ((bits >> 4) & 0x0f0f0f0f);
	bits = (bits & 0x00ff00ff) + ((bits >> 8) & 0x00ff00ff);
	bits = (bits & 0x0000ffff) + ((bits >> 16) & 0x0000ffff);
	return bits;
}

• 分治统计：依次将相邻 2bits、 4bits 分组，计算组内 1数量
  • 移位、求并：将组内无效 bits 置 0、并对齐
  • +：计算组内 1 数量
    • 0x0 + 0x0 = 0x0
    • 0x0 + 0x1 = 0x1
    • 0x1 + 0x1 = 0x10：进位，符合逻辑
• 改进方式：考虑避免不必要的 &
  • 根据进位特性替换 2bits 组对应语句
  • 考虑组内空位是否可容纳 + 后结果
    • 8bits 组：有效半组 4bits 足够存储中的最大 1 数量 8，但 无法存储 16 或更大， 需要及时置空无效bit
    • 16bits 组及之后：有效半组足够存储最大 1 数量 32，可以 计算完之后再取值

1
2
3
4
5
6
7
8
9
10
11

int population(unsigned int bits){
	// 等于上述首行
	bits = bits - ((bits >> 1) & 0x55555555);
	bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
	// 4bits 足够存储组内 8bits 中 `1` 最大数量 8
	bits = (bits + (bits >> 4)) & 0x0f0f0f0f;
	// 8bits 足够存储全部 32bits 中 `1` 最大数量 32
	bits = bits + (bits >> 8);
	bits = bits + (bits >> 16);
	return bits & 0x3f
}

奇偶性

• 目标：判断 unsigned 二进制表示中 1 数量奇偶性
• 思路方向
  • 移位遍历，注意语言特性
    • 逻辑移位和算术移位
    • 求余结果
  • 分治统计

分治统计

1
2
3
4
5
6
7
8
9
10
11
12

// 原始版本
unsigned char parity(unsigned int i){
	// 相邻2bit一组异或确定奇偶
	i = i ^ (i >> 1);
	// 相邻4bit一组，依赖以上结果确定奇偶
	i = i ^ (i >> 2);
	i = i ^ (i >> 4);
	i = i ^ (i >> 8);
	i = i ^ (i >> 16);
	// 奇偶性保存在最后1bit，取出
	return i & 0x1;
}

• 分治统计：依次将相邻 2bits、 4bits 分组，统计组内奇偶性
  • 分组方式顺序调换仅影响中间结果中存放奇偶性统计结果 bits 位置
    • 奇偶性统计结果存放在组内最后 bit
    • 其中每次分组统计事实上都是统计 2bits 的奇偶性
• 改进方式
  • 调整分组顺序，将存储奇偶性 bits 位置移至最后
  • 计算奇偶性 bits 对应奇偶性表，查表得到结果
    • 一般可以设置长度为 0x0f 长度的数组，其中取值为索引奇偶性
    • 0x6996 即为对应奇偶性表，其中各位序 bit 取值为位序值对应 的奇偶性

1
2
3
4
5
6
7
8
9

// 改进版本
unsigned char parity_k(unsigned int i){
	// 将存储奇偶性 bits 移至最后
	i = i ^ (i >> 4);
	i = i ^ (i >> 8);
	i = i ^ (i >> 16);
	// 查表得到结果
	return (0x6996 >> (i & 0x0f )) & 0x01;
}

奇偶性填充

• 目标：将 unsigned char 中最高位作为校验位，保证整体的二进制标表示的奇偶性
• 思路方向
  • 求1数量并设置标志位
  • 按位乘积后取模

取模

1
2
3
4
5
6

unsigned char even(unsigned char i){
	return ((i * 0x10204081) & 0x888888ff) % 1920;
}
unsigned char odd(unsigned char i){
	return ((i * 0x00204081) | 0x3DB6DB00) % 1152;
}

• 各数字二进制含义（设 i 的二进制表示为 abcdefg）
  • 0x10204081 * i 得到 i 二进制重复 5 次（溢出被截断）
  • 0x888888ff & 抽取所需 bits d000a000e000b000f000c000gabcdefg
  • 1920 = 15 * 128：对其取模即得到[X]abcdefg （将被除数表示为 16 进制分块可证）

位元反序

• 目标：返回 6bits 长二进制的反序

1
2
3

unsigned char revert(unsigned char i){
	return ((i * 0x00082082) & 0x01122408) % 255;
}

• 各数字二进制含义（设 i 的二进制表示为 abcdef）
  • 0x00082082 * i 得到 i 二进制重复 4 次
  • 0x01122408 & 抽取所需 bits 0000000a000e00b000f00c000000d000
  • 对 255 取模即得到反序*（将被除数表示为 256 进制分块可证）

前导 0

• 目标：获取 unsigned 的二进制表示中前导 0 数量
• 思路方向
  • 移位遍历
  • 区间映射：将原始 unsigned 映射为较小范围的取值

区间映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

unsigned char nlz(unsigned int i){
	static unsigned char table[64] = {
		32, 31, 'u', 16, 'u', 30, 3, 'u', 15, 'u', 'u', 'u', 29,
		10, 2, 'u', 'u', 'u', 12, 14, 21, 'u', 19, 'u', 'u', 28,
		'u', 25, 'u', 9, 1, 'u', 17, 'u', 4, 'u', 'u', 'u', 11,
		'u', 13, 22, 20, 'u', 26, 'u', 'u', 18, 5, 'u', 'u', 23,
		'u', 27, 'u', 6, 'u', 24, 7, 'u', 8, 'u', 0, 'u'
	}

	i = i | (i >> 1);
	i = i | (i >> 2);
	i = i | (i >> 4);
	i = i | (i >> 8);
	i = i | (i >> 16);
	i = i * 0x06eb14f9;
	return table[i >> 26];
}

• 区间映射
  • 移位取或：将最高位 1 传播至所有低位，原始值映射至 33 种取值
  • 0x06eb14f9：将 33 种值映射为低 6 位取值均不同值
    • 此类数的共同特点是因子均为 $2^k \pm 1$ （此类数乘法容易通过移位操作实现）
    • 最小的此性质的数为 0x45bced1 = 17 * 65 * 129 * 513

速算

无符号整形除法

• 目标：大部分计算机架构中除法耗时，寻找方法将特定除数的除法转换为 其他指令
• 思路：除数为常数时，用移位、乘法、加法替代除法运算
  • 常数除法（有符号或无符号）基本都有对应的乘法版本
  • 注意类型溢出

除数为3

1
2
3
4
5

unsigned div3(unsigned int i){
	// 在更高级别优化过程实际就会转化为类似指令
	// 但此语句可能会导致类型溢出
	return (i * 2863311531) >> 33;
}

快速求平方根倒数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

float i_sqrt(float a){
	union {
		int ii;
		float i;
	};
	i = a;
	float ihalf = 0.5f * i;

	// 得到较好的初始估算值
	ii = 0x5f000000 - (ii >> 1);

	// 牛顿法迭代，可以重复以下语句多次提高精度
	i = i * (1.5f - ihalf * i * i);

	return i;
}

• 移位获取初始值

  • 考虑（规格化）单精度浮点数 $a$ 的二进制表示

    $$\begin{align*} a &= 2^{E-127} * (1+F) \\ \frac 1 {\sqrt a} &= 2^{\frac {127 - E} 2 + 127} * (1+F)^{-\frac 1 2} \\ &= 2^{190.5 - \frac E 2} * (1+F)^{-\frac 1 2} \end{align*}$$

  • 则 0x5f000000 - (ii >> 1) 可以满足指数部分得到近似结果 $190 - \frac E 2$

  • 其他细节使得存在比 0x5f000000 实践更优值，如：0x5f375a86
    • 规格化值的底数接近 1
    • 移位运算指数最后位部分移至尾数
    • 减法运算尾数部分向指数借位

• 牛顿法：$x{n+1} = xn - \frac {f(x_n)} {f^{‘}(x__n)}$

  • 求 $\frac 1 {\sqrt x}$，即求 $f(x) = x^{-2} - a$ 零点
  • 则迭代为 $x{n+1} = xn(1.5 - 0.5 a x__n^2)$

• http://www.lomont.org/papers/2003/InvSqrt.pdf
• https://zhuanlan.zhihu.com/p/33543750

最长公共子串

求两个字符串s1、s2（长度分别为m、n）最长公共子串长度

矩阵比较

• 将两个字符串分别以行、列组成矩阵M

• 对矩阵中每个元素$M[i, j]$，若对应行、列字符相同

  • 元素置为1，否则置0

  • 置元素$M[i,j] = M[i-1, j-1] + 1$，否则置0

• 则矩阵中最长的非0斜序列对应子串即为最长公共子串

算法特点

• 时间效率$\in \Theta(mn)$
• 输入增强

最长公共子序列

求两个序列X、Y的最长公共子序列

• 子序列：去掉给定序列中部分元素，子序列中元素在原始序列中 不必相邻
• 最长公共子序列可能有很多

动态规划

• 先使用动态规划确认最长子序列长度，构造动态规划表

  $$C[i,j] = \left \{ \begin{array}{l} 0 & i=0 或 j=0 \\ C[i-1, j-1] & i,j > 0 且 X[i] == Y[j] \\ max\{C[i-1, j], C[i, j-1]\} & i,j > 0 且 X[i] != Y[j] \\ \end{array} \right.$$

  • $C[i,j]$：序列X前i个元素子序列、序列Y前j个元素子序列 最大子序列长度

• 根据动态规划表找出最长公共子序列

  

  • 从动态规划表中首个格子开始，沿着某条格子路径达到 表中最后一个元素
  • 路径中值改变格子对应序列中元素即为最长公共子序列中 元素

  • 不同格子路径可能找到不同的最长公共子序列

算法特点

• 时间效率

  • 动态规划部分$\in \Theta(|X||Y|)$
  • 生成公共子序列部分$\in Theta(|X|+|Y|)$

• 动态规划

最长升/降序序列

寻找长度为N的序列L中最长单调自增子序列

最长公共子序列法

• 将原序列升序排序后得到$L^{ * }$
• 原问题转换为求$L, L^{ * }$最长公共子序列

算法特点

• 时间效率：$\in \Theta(|L|^2)$

动态规划法

• 使用动态规划法求出以$L[i]$结尾的最长升序子序列长度， 得到动态规划表

  $$C[i] = \left \{ \begin{array}{l} max\{C[j]\} + 1, j=1,\cdots,i-1, L[j]<L[i] & i \geq 2 \\ 1 & i=1 \end{array} \right.$$

  • $C[i]$：以$L[i]$结尾的最长升序子序列长度

• 则动态规划表中值最大者即为最长升序序列长度

算法特点

• 时间效率$\in O(|L|^2)$

动态规划2

使用线性表记录当前能够找到的“最长上升子序列”

• 若当前元素大于列表最后（大）元素：显然push进线性表

  • 则当前线性表长度就是当前子串中最长上升子序列

• 若当前元素不大于列表中最后元素

  • 考虑其后还有元素，可能存在包含其的更长上升序列
  • 使用其替换线性表中首个大于其的元素
    • 隐式得到以当前元素为结尾的最长上升子序列：其及 其之前元素
    • 更新包含其的上升子序列的要求：之后元素大于其
  • 不影响已有最长上升子序列长度，且若之后出现更长上升 子序列，则线性表被逐渐替换

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

lengthOfLIS(nums[0..n-1]):
	// 动态规划求解最上升子序列
	// 输入：序列nums
	// 输出：最长上升子序列长度
	if n == 0:
		return 0
	LIS = InitVector()
	for num in nums:
		if num > LIS.last()
			LIS.push(num)
		else:
			for idx=0 to LIS.len():
				if num <= LIS[idx]:
					break
			LIS[idx] = num
				// 更新上升子序列中首个大于当前元素的元素
	return LIS.len()

动态规划+二分

最长回文子串

中心扩展法

• 遍历串，以当前元素为中心向两边扩展寻找以回文串

• 为能找到偶数长度回文串，可以在串各元素间填充空位

  

  • 填充后元素位置$i = 2 i + 1$、填充符位置$2 i$
  • 两端也要填充：否则可能出现#为中心回文和端点回文 等长，但返回#中心回文
  • 填充后得到最长回文串肯定是原最长回文串扩展
    • 非#中心：原串不存在偶数长度回文串更长，则显然
    • #中心：显然

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

LongestSubParlidrome(nums[0..n-1]):
	// 中心扩展法求解最长回文子串
	// 输入：串nums[0..n-1]
	// 输出：最长回文串
	nnums = padding(nums)
	nn = len(nnums)
	max_shift, center = 0, -1
	for i=0 to nn:
		shift = 1
		while i >= shift and i + shift < nn:
			if nnums[i-shift] != nnums[i+shift]:
				break
			shift += 1

		// 越界、不匹配，均为-1得到正确、有效`shift`
		shift -= 1

		if shift > max_shift:
			max_shift, center = shift, i

	left = (center - max_shift + 1) // 2
	right = (center + max_shift) // 2
	return nums[left : right]

特点

• 算法效率
  • 时间复杂度$\in O(n^2)$
  • 空间复杂度$\in O(1)$

动态规划

Manacher算法

• 考虑已经得到的以$i$为中心、半径为$d$回文子串对称性

  • 则$[i-d, i+d+1)$范围内中回文对称
  • 即若$i-j, j<d$为半径为$dd$的回文串中心，则$2i - j$ 同样为半径为$dd$的回文串中心 （$[i-d, i+d-1)$范围内）

• 所以可以利用之前回文串信息减少之后回文串检测

• Manacher算法同样有中心扩展算法问题，要填充检测偶数长串

算法

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

LongestSubParlidrome(nums[0..n-1]):
	// Manacher算法利用之前回文串信息求解最长回文子串
	// 输入：串nums[0..n-1]
	// 输出：最长回文串
	nnums = padding(nums)
	nn = len(nnums)
	shift_d = [0] * nn
	max_shift, center = 0, 0
	for i=0 to nn:

		// 利用之前信息初始化
		shift = shift_d[i]

		while shift <= i and shift < nn - i:
			if nnums[i+shift] != nnums[i - shift]:
				break
			shift += 1
		shift -= 1

		// 更新可利用信息
		for j=1 to shift:
			shift_d[i+j] = max(
				shift_d[i+j],
				min(shift_d[i-j], i+j-shift))

		if shift > max_shift:
			max_shift, center = shift, i

	left = (center - max_shift + 1) // 2
	right = (center + max_shift) // 2
	return nums[left: right]

特点

• 算法效率
  • 时间复杂度$\in \Theta(n)$
  • 空间复杂度$\in \Theta(n)$

总述

• 寻找（明确地、隐含地）寻找一个组合对象

  • 排列
  • 组合（整数规划）
  • 子集

• 这些对象能满足特定条件并具有想要的属性

  • 价值最大化
  • 成本最小化

特点

无论从理论角度、实践角度而言，组合问题是计算领域最难的问题

• 随着问题规模增大，组合对象数量增长极快

• 没有一种已知算法，能在可接受的时间范围内，精确的解决 大部分组合问题，且被普遍认为不存在（未被证实）

• 有些组合问题有高效求解算法，是幸运的例外

从更抽象的角度看，旅行商问题、图填色问题也是组合问题的特例

思路

• exhaustive search：（穷举搜索）是简单的蛮力方法

  • 生成问题域每个元素
  • 选出满足问题约束的元素
  • 最后寻找期望元素

• 因为可能性太多，基本可能从动态规划方向着手

背包问题

给定n个重量为$w_1, w_2, \cdots, w_n$价值为$v_1, v_2, …, vn$ 的物品和承重为$W$的背包，求能够装进背包的最有价值物品子集

蛮力算法

算法

• 考虑所有n个物品的子集
• 计算每个子集重量，找出可行子集
• 找到可行子集中价值最大子集

经典自底向上动态规划

依次求解所有子问题、记录

算法

设$F(i, j)$为由前i个物品、承重量为j的背包得到最优解

• 不包括第i个物品的子集中，最优子集价值为$F(i-1, j)$

• 包括第i个物品的子集中，最优子集是由该物品和前i-1个物品 中能够放进承重量为$j-w_i$的背包的最优子集组成，总价值为 $v_i + F(i-1, j-w_i)$

则递推式为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Knapsack(Ws[1..n], Vs[1..n], W)
	// 动态规划求解背包问题
	// 输入：Ws[1..n]物品重量、Vs[1..n]物品价值，W背包承重
	// 输出：背包能够装载的最大价值
	for i = 0 to n do
		F[i, 0] = 0
	for j = 0 to W do
		F[0, j] = 0
		for i = 1 to n do
			if j >= Ws[i]:
				F[i, j] = max(F[i-1, j], Vs[i] + F[i-1, j-Ws[i])
				// 这里用于比较的F值，在之前的循环中已经确定
			else
				F[i, j] = F[i-1, j]
	return F[n, W]

算法特点

• 算法效率
  • 时间效率$\in \Theta(nW)$
  • 空间效率$\in \Theta(nW)$
  • 回溯求最优解组成效率$\in O(n)$

自顶向下动态规划

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

MFKnapsack(i, j)
	// 背包问题的记忆功能方法
	// 输入：i考虑的物品数量，j背包承重
	// 输出：前i个物品的最优可行子集
	// Ws[1..n]、Vs[1..n]、F[0..n, 0..W]作为全局变量
	for i = 0 to n do
		F[i, 0] = 0
	for j = 0 to W do
		F[0, j] = 0
	if F[i, j] < 0
		if j < Ws[i]
			value = MFKnapsack(i-1, j)
		else
			value = max(MFKnapsack(i-1, j),
				Vs[i] + MFKnapsack(i-1, j - Ws[i]))
		F[i, j] = value
	return F[i, j]

算法特点

• 算法效率
  • 相较于经典自底向上算法，时间效率提升常数因子，但是 效率仍然$\in \Theta(nW)$
  • 相较于自底向上算法空间优化版版本而言，空间效率较低

分支界限法

• 不失一般性认为，物品按照价值重量比$v_i / w_i$降序排列， 可以简化问题

• 第i层节点上界可取$ub = v + (W - w)(v{i+1} / w{i+1})$

  • $v$：已选物品价值
  • $W - w$：背包剩余承重量
  • $v{i+1}/w{i+1}$：剩余物品单位单位最大价值

• 更紧密、复杂的上界 $ub = v + \sum{k=i+1}^K v_k + (W - \sum{k=1}^K w_k)v_K / w_K$

算法

特点

• 分支界限法求解背包问题中，每个中间节点都是给定物品的子集 ，是背包问题的可行解

背包问题近似算法

贪婪算法

算法

• 对物品按照价值重量比$r_i = v_i / w_i, i=1,2,\cdots,n$ 降序排列

• 重复以下直到有序列表中不留下物品

  • 如果列表中当前物品可以装入，则放入背包并处理下个物品
  • 否则忽略，直接处理下个物品

特点

• 原始的贪婪算法解的精确率没有上界

  • 考虑：承重量为$W$背包，如下物品

    |物品|重量|价值|价值/重量| |——-|——-|——-|——-| |1|1|2|2| |2|w|w|1|

  • 则近似解精确率$r(s_a) = W/2$无上界

• 增强版贪婪算法：取贪婪算法解、能装载的价值最大单个物品 价值中较大者

  • 此改进的性能比可以降到2

近似方案

背包问题的存在多项式时间的系列算法，可以调节算法中参数$k$ 得到满足任意预定义精确率的近似解$s_a^{(k)}$

Sahni方案

• 生成所有小于k个物品的子集
• 向贪婪算法一样，向每个能装入背包的子集添加剩余物品中 价值重量比最大者
• 得到最有价值的修改后子集作为结果返回

Fully Polynomial Scheme

完全多项式方案

特点

• Sahni方案理论意义远大于实用价值

  • 其效率$\in O(kn^{k+1})$是n的多项式函数
  • 但是是k的指数函数

• 完全多项式方案更加复杂，但没有效率为参数k指数的缺陷

Bin-Packing Problem

装箱问题：给定n个问题，大小都是不超过1的有理数，将其装进数量 最少的大小为1的箱子中

Graph-Coloring Problem

图着色问题：对给定图，求使得任何两个相邻顶点颜色都不同时， 需要分配给图顶点的颜色数量

划分问题

给定n个正整数${a_i, i=1,2,\cdots}，判定能够将其划分为和相等 的两个子集

Subset-Sum Problem

给定n个正整数${a_i, i=1,2,\cdots}$，求子集$S$和为正整数d

回溯算法

约束

• 其中$s$为考虑考虑第i+1元素时，前i个元素选情况下的和

算法

• 假设集合元素按升序排列

• 根节点为未选择任何元素

• 依次考虑将元素$a_i$添加进子集S中

  • 若满足约束条件、下个元素未考虑，继续考虑
  • 否则回溯，重新考虑父母节点

• 直到找到子集满足和为d，或第二次回溯到根节点

特点

币值最大化

给定一排n个硬币，币值为正整数$c_i, i=1, 2, \cdots, n$（币值 不唯一），在原始位置不相邻的情况下，使得所选硬币总金额最大

动态规划

算法

记最大可选金额为$F(n)$将可行规划分为两组

• 包含最后一枚硬币，最大金额为$c_n + F(n-2)$
• 不包含最后一枚硬币，最大金额为$F(n-1)$

则递推方程为

1
2
3
4
5
6
7
8
9

CoinRow(C[1..n])
	// 在所选硬币不相邻，从一排硬币中选择最大金额
	// 输入：C[1..n]保存n个硬币面值
	// 输出：可选硬币最大金额
	F[0] = 1
	F[1] = C[1]
	for i = 2 to n do
		F[i] = max(C[i] + F[i-2], F[i-1])
	return F[n]

算法特点

• 时间效率$\in \Theta(n)$
• 空间效率$\in \Theta(n)$

找零问题

需找零金额为n，最少需要多少面值为$d_1 < d_2 < \cdots < d_n$ 的硬币，考虑$d_1 = 1$的一般情况

动态规划

算法

记$F(n)$为总金额为n的数量最少的硬币数目，定义$F(0)=0$

• 得到n的途径只能是在$n-d_j$上加入面值为$d_j$的硬币，其中 $j=1, 2, \cdots, m$，且$n \geqslant d_j$

• 考虑所有满足条件$d_j$，选择使得且$F(n - d_j)$最小者

则递推式有

1
2
3
4
5
6
7
8
9
10
11
12
13

ChangeMaking(D[1..m], n)
	// 动态规划法求解找零问题，d_1 = 1
	// 输入：正整数n，币值数组D[1..m]
	// 输出：总金额为n的最少硬币数目
	F[0] = 0
	for i = 1 to n do
		tmp = \infty
		j = 1
		while j <= m and i >= D[j] do
			tmp = min(F[i-D[j], tmp)
			j += 1
		F[i] = tmp + 1
	return F[n]

硬币收集问题

在n * m格木板中存放有硬币，每格硬币最多一个，寻找左上角(1,1) 到右下角(n, m)路径，使得能够收集尽可能多硬币，每次只能向下、 向右移动

动态规划

算法

记$F(i, j)$为截止到第i行、第j列单元格$(i, j)$能够收集到最大 硬币数

• 单元格$(i, j)$只能经由$(i-1, j)$、$(i, j-1)$达到
  • 初值1：假定$F(0, j)=0, F(i, 0)=0$
  • 初值2；递推求解$F[1, j], F[i, 1]$

则递推方程为

1
2
3
4
5
6
7
8
9
10
11
12
13
14

CoinCollection(C[1..n, 1..m])
	// 动态规划算法求解硬币收集问题
	// 输出：矩阵C[1..n, 1..m]表示单元格是否有硬币
	// 输出：在单元格[n, m]能够收集到的最大硬币数
	F[1, 1] = C[1, 1]
	for j = 2 to m do
		F[1, j] = F[1, j-1] + C[1, j]
		// 初始化首行
	for i = 2 to n do
		F[i, 1] = F[i-1, 1] + C[i, 1]
		for j = 2 to n do
			// 先填列
			F[i, j] = max(F[i-1, j], F[i, j-1]) + C[i, j]
	return F[n, m]

算法特点

• 算法效率
  • 计算每个单元格$F[i, j]$花费常量时间，所以算法时间 效率$\in \Theta(nm)$
  • 算法空间效率$\in Theta(nm)$

n皇后问题

将n个皇后放在$n * n$的棋盘上，使得皇后之间不能相互攻击

回溯算法

算法

算法特点

说明

• $n \geqslant 4$的n皇后问题都可以在线性时间内求解，已经 找到一些可选公式，用于计算n皇后的位置

生成排列

生成集合排列问题可以抽象为生成${1,\cdots,n}$所有$n!$个排列的 问题

• 假设$(n-1)!$个排列已经生成
• 则可以把n插入n-1个元素中可能的n个位置中去，得到较大规模 问题的解

最小变化

• 在元素上使用小箭头标记其方向： $\overleftarrow 1 \overleftarrow 2 \overleftarrow 3$
• 如果元素k的箭头指向相邻的较小元素，称在此排列中是移动的

减常量法

1
2
3
4
5
6
7
8
9
10

JohnsonTrotter(n)
	// 生成排列
	// 输入：正整数n
	// 输出：{1..n}所有排列列表
	将第一个排列初始化
	while 存在一个移动元素 do
		求最大的移动元素k
		把k和其箭头指向的相邻元素互换
		调转所有大于k的元素的方向
		将新排列添加到列表中

算法特点

• JsonTrotter是生成排列最有效算法之一，其运行时间和排列 数量成正比，即$\in \Theta(n!)$

字典序

减常量法

• 找到序列中最长递减后缀 $a{i+1} > a{i+2} > \cdots > a_{n}$
• 将$a_i$同序列中大于其的最小元素交换
• 将新后缀颠倒，使其变为递增序列，加入列表中

1
2
3
4
5
6
7
8
9
10
11
12
13

LexicographicPermute(n):
	// 以字典序产生排列
	// 输入：正整数n
	// 输出：字典序下，所有排列列表
	初始化第一个排列为12...n
	while 最后一个排列有两成连续升序元素 do
		找出使得a_i < a_{i+1}的最大的i
			// 即找到最长递减后缀
		找到使得a_i < a_j的最大索引
			// 即在后缀中大于其的最小元素索引
		交换a_i和a_j
		将a_{i+1}和a_{n}的元素反序
		将新排列添加至列表中

生成子集

集合$A[a_1, \cdots, a_n}$的所有子集可以分为两组

• 包含$a_n$：${a_1, \cdots, a_n}$的所有子集
• 不包含$a_n$的子集：把$a_n$添加进${a_1, \cdots, a_n}$子集 获得

• 同样的可以把集合抽象为位串，每个位串表示一个子集

减常量算法

字典序

按生成字典序（位串字典序）生成子集

• 将正序${1..n}$转换为二进制位串
• 依次按照二进制位串生成子集
  • 位串中为1表示对应元素在子集中

挤压序

按照挤压序（位串挤压序）生成子集

• 将倒序{n..1}转换为二进制位串
• 依次按照二进制位串生成子集
  • 位串中为1表示对应元素在子集中

Squashed Order：所有包含$aj$子集必须紧排在所有包含 $a_1, \cdots, a{j-1}$的子集之后

最小变化

每个子集和其直接前趋之间，要么增加一个元素，要么减少一个元素

• 即每个位串和直接前趋之间仅仅相差一位

1
2
3
4
5
6
7
8
9
10
11
12
13

BRGC(n)
	// 递归生成二进制反射格雷码
	// 输入：正整数n
	// 输出：所有长度为n的格雷码位串列表
	if n == 1
		表L包含位串0、位串1
	else
		调用BRGC(n-1)生成长度为n-1的位串列表L1
		表L1倒序后复制给表L2
		把0加到表L1每个位串前
		表1加到表L2每个位串前
		把表L2添加到表L1后得到表L
	return L

球、桶问题

n个球放入m个桶中情况数量

球同、桶不同、无空桶

• 插板法

  $$\left \{ \begin{array}{l} C_{n-1}^{m-1}, & n \geq m \\ 0, & n < m \end{array} \right.$$

球同、桶不同、可空桶

• 插板法：可以假设m个桶中已经放好球，即m+n个相同球放入m个 不同桶、不允许空桶

  $$C_{n+m-1}^{m-1}$$

球同、桶同、可空桶

• 动态规划

  $$dp_4[i][j] = \left \{ \begin{array}{l} dp_4[i][j-1] + dp_4[i-j][j], & i \geq j \\ dp_4[i][j-1], & i < j \\ 1, & i=1,0 or j=1 \end{array} \right.$$

• 球数$i \geq j$桶数时递推式

  • 若有桶均包含球：剩余球可能性$dp[i-j][j]$
  • 若存在桶不包含球：剔除一个桶不影响总数
  • 没有其余情况

球同、桶同、无空桶

• 动态规划：由$dp_4$得到

  $$dp_5[i][j] = \left \{ \begin{array}{l} dp_4[i-j][j], & i \geq j \\ 0, & i < j \end{array} \right.$$

球不同、桶同、无空桶

• 第二类斯特林数

  $$dp[i][j] = \left \{ \begin{array}{l} j*dp[i-1][j] + dp[i-1][j-1], & 1 \leq j < i \\ 1, & i = j \\ 0, & i < j \end{array} \right.$$

• 球数$i>j$桶数时递推式

  • 考虑前$i-1$球已经占满所有桶，则最后球放入任何桶都是 新情况
  • 考虑前$i-1$只占满$j-1$个桶，则最后球必须放入空桶
  • 其他情况不可能

球不同、桶同、可空桶

• 在球不同、桶同、无空桶情况下枚举不空桶数目

  $$dp_2[i][j] = \sum_{k=1}^j dp[i][j]$$

球不同、桶不同、无空桶

• 在球不同、桶同、无空桶情况下对桶排序

  $$dp_3[i][j] = dp[i][j] * (j!)$$

球不同、桶不同、可空桶

• 每个球都有m中选择：$m^n$

总述

在给定的集合、多重集（允许多个元素具有相同的值）中找给定值 （查找键，search key）

• 顺序搜索
• 折半查找：效率高但应用受限
• 将原集合用另一种形式表示以方便查找

评价

没有任何一种查找算法在任何情况下都是最优的

• 有些算法速度快，但是需要较多存储空间
• 有些算法速度快，但是只适合有序数组

查找算法没有稳定性问题，但会发生其他问题

• 如果应用里的数据相对于查找次数频繁变化，查找问题必须结合 添加、删除一起考虑

• 必须仔细选择数据结构、算法，以便在各种操作的需求间达到 平衡

无序线性表查找

顺序查找

算法

• 将给定列表中连续元素和给定元素查找键进行比较
  • 直到遇到匹配元素：成功查找
  • 匹配之前遍历完整个列表：失败查找

1
2
3
4
5
6
7
8
9
10
11
12

SequentialSearch(A[0..n-1], K)
	// 顺序查找，使用**查找键作限位器**
	// 输入：n个元素数组A、查找键K
	// 输出：第一个值为K的元素位置，查找失败返回-1
	A[n] = K
	i = 0
	while A[i] != K do
		i = i + 1
	if i < n
		return i
	else
		return -1

改进

• 将查找键添加找列表末尾，查找一定会成功，循环时将不必每次 检查是否到列表末尾
• 如果给定数组有序：遇到等于（查找成功）、大于（查找失败） 查找键元素，算法即可停止

二叉查找树

算法

• 对数组构建二叉查找树
• 在二叉查找树上进行查找

特点

• 算法效率：参见二叉查找树

• 构建二叉查找树（插入）和查找操作基本相同，效率特性也相同

• 减可变规模 + 输入增强

预排序查找

对线性表预排序，有序表中查找速度快得多

算法

1
2
3
4
5
6
7

PreorderSearch(A[0..n-1])
	// 对数组预排序然后查找
	// 输入：可排序数组A[0..n-1]
	// 输出：元素在数组中的位置
	对B[(数组元素, 索引)]进行预排序
	使用折半查找寻找二元组
	返回二元组中索引

特点

• 算法时间效率：取决于排序算法

  • 查找算法在最差情况下总运行时间$\in \Theta(nlogn)$
  • 如果需要在统一列表上进行多次查找，预排序才值得

• 这种预排序思想可以用于众数、检验惟一性等， 此时算法执行时间都取决于排序算法 （优于蛮力法$\in \Theta(n^2)$）

• 变治法（输入增强）

预排序检验唯一性

1
2
3
4
5
6
7
8
9

PresortElementUniqueness(A[0..n-1])
	// 先对数组排序，求解元素唯一性问题
	// 输入：n个可排序元素构成数[0..n-1]
	// 输出：A中有相等元素，返回true，否则false
	对数组排序
	for i=0 to n-2 do
		if A[i] = A[i+1]
			return false
	return true

预排序求众数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

PresortMode(A[0..n-1])
	// 对数组预排序来计算其模式（众数）
	// 输入：可排序数组A[0..n-1]
	// 输出：数组模式
	对数组A排序
	i = 0
	modefrequency = 0
	while i <= n-1 do
		runlength = 1
		runvalue = A[i]
		while i + runlength <= n-1 and A[i+runlength] == runvalue
			// 相等数值邻接，只需要求出邻接次数最大即可
			runlength = runlength+1
		if runlength > modefrequency
			modefrequency = runlength
			modevalue = runvalue
		i = i+runlength

	return modevalue

有序顺序表查找

• 有序顺序表的查找关键是利用有序减规模

• 但关键不是有序，而是减规模，即使顺序表不是完全有序， 信息足够减规模即可

折半查找/二分查找

二分查找：利用数组的有序性，通过对查找区间中间元素进行判断， 缩小查找区间至一般大小

• 依赖数据结构，需能够快速找到中间元素，如数组、二叉搜索树

• 一般模板：比较中间元素和目标的大小关系、讨论

  1 2 3 4 5 6 7 8 9

  left, right = ... while condition(search_space is not NULL): mid = (left + right) // 2 if nums[mid] == target: // do something elif nums[mid] > target: // do something elif nums[mid] < target: // do somthing

  • 函数独立时，找到target可在循环内直接返回
  • 函数体嵌入其他部分时，为方便找到target应break， 此时涉及跳出循环时target可能存在的位置
    • 找到target中途break
    • 未找到target直到循环终止条件

基本版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

BinarySearchEndReturnV1(nums[0..n-1], target):
	// 非递归折半查找基本版，不直接返回，方便嵌入
	// 输入：升序数组nums[0..n-1]、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = 0, n-1
	while left <= right:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid+1
		else:
			right = mid-1
	else:
		assert(mid == right == left-1)

	# 仅最后返回，方便嵌入，下同
	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = 0, n-1

  • 左、右均未检查、需检查
  • 即代码中查找区间为闭区间$[left, right]$，此时 搜索区间非空

• 中点选择：mid = (left + right) // 2

  • 向下取整
  • 对此版本无影响，left、right总是移动，不会死循环

• 循环条件：left <= right

  • 搜索区间为闭区间，则相应检查条件为left <= right， 否则有元素未被检查
  • 在循环内left、right可能重合

• 更新方式：left=mid+1, right=mid-1

  • 为保证搜索区间始终为闭区间，需剔除mid

• 终止情况：right=left-1、mid=left/right

  • 循环条件、循环内部+1保证：上轮循环left==right
  • 越界终止情况：左、右指针均剔除mid，两侧均可能越界
    • mid=right=n-1, left=n
    • mid=left=0, right=-1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • target位于[right, left]间
    • left=mid+1=right+1表示小于target元素数量

• 需要和左右邻居（查找结束后）、left、right比较 情况下，容易考虑失误，不适合扩展使用

高级版1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BinarySearchV2(nums[0..n-1], target):
	left, right = 0, n
	while left < right:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid+1
		else:
			right = mid
	else:
		assert(mid-1 == left == right)

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = 0, n

  • 左未检查、需检查，右无需检查
  • 即代码中查找区间为左闭右开区间$[left, right)$

• 中点选择：mid = (left + right) // 2

  • 向下取整
  • 此处必须选择向下取整，否则left=right-1时进入死循环
  • 即：循环内检查所有元素，取整一侧指针必须移动

• 循环条件：left < right

  • 搜索区间为左闭右开区间，则检查条件为left < right， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid+1, right=mid

  • 为保证搜索区间始终为左闭右开区间
    • 移动左指针时需剔除mid
    • 移动右指针时无需剔除mid

• 终止情况：right=left、mid=left/left-1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
    • left=mid=right-1
  • 越界终止情况：仅左指针剔除mid，仅可能右侧越界
    • left=right=n=mid+1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • left=mid=right：循环过程中target可能已不在 搜索区间中，最终位于(mid-1, mid)
    • mid+1=left=right：(mid, left)
    • left表示小于target元素数量

高级版2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BainarySearchEndReturnV3(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = -1, n
	while left < right:
		mid = (left + right + 1) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			right = mid-1
		else:
			left = mid

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = -1, n-1

  • 左无需检查，右未检查、需检查
  • 即代码中查找区间为左开右闭区间$(left, right]$

• 中点选择：mid = (left + right + 1) // 2

  • 向上取整
  • 此处必须选择向上取整，否则left=right-1时进入死循环 （或放宽循环条件，添加尾判断）
  • 即：循环内检查所有元素，取整一侧指针必须移动

• 循环条件：left < right

  • 搜索区间为左开右闭区间，则检查条件为left < right， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid, right=mid+1

  • 为保证搜索区间始终为左闭右开区间
    • 移动右指针时需剔除mid
    • 移动左指针时无需剔除mid

• 终止情况：left=right、mid=left/left+1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
    • left+1=mid=right
  • 越界终止情况：仅右指针剔除mid，仅可能左侧越界
    • left=right=-1=mid-1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • left=mid=right：循环过程中target可能已不在 搜索区间中，最终位于(right, right+1)
    • mid+1=left=right：(left, right)
    • left+1表示小于target元素数量

高级版3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BinarySearchEndReturnV2(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = -1, n
	while left < right-1:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid
		else:
			right = mid

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = -1, n

  • 左、右均无需检查
  • 即代码中查找区间为开区间$(left, right)$

• 中点选择：mid = (left + right) // 2

  • 向下取整、向上取整均可

• 循环条件：left < right-1

  • 搜索区间为左开右闭区间，则检查条件为left < right-1， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid, right=mid

  • 循环终止条件足够宽泛，不会死循环

• 终止情况：left=right-1、mid=right/right-1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
  • 越界终止情况：左右初始条件均越界，则左、右均可能越界
    • mid=left=n-1、right=n
    • left=-1、mid=right=0

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • target始终在搜索区间(left, right)内
    • 最终位于(left, right)

高级版1-原

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

BinarySearchKeep1(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = 0, n-1

	while left < right - 1:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			right = mid
		else:
			left = mid

	// post-procesing
	if nums[left] == target:
		return left
	if nums[right] == target:
		return right

	return -1

• 初始条件：left = 0, right = n-1
• 终止情况：left = right - 1
• 指针移动：left = mid, right= mid

• 关键特点

  • n>1时left、mid、right循环内不会重合
  • mid可以left、right任意比较，无需顾忌重合
  • 需要和左右邻居、left、right比较时适合使用
  • 扩展使用需要进行真后处理，对left、right进行判断

• 终止情况：left = right - 1

  • 循环过程中会保证查找空间至少有3个元素，剩下两个 元素时，循环终止
  • 循环终止后，left、right不会越界，可以直接检查

• target位置

  • 若存在target，可能位于mid、left、right

    • mid：因为找到nums[mid]==target跳出
    • left：left=0，循环中未检查
    • right：right=n-1，循环中未检查

  • 不存在target，则target位于(left, right)之间

  • 适合访问目标在数组中索引、极其左右邻居

• 仅仅二分查找的话，后处理其实不能算是真正的后处理

  • nums[mid]都会被检查，普通left、right肯定不会 是target所在的位置

  • 真正处理的情况：target在端点

    • left=0, right=1终止循环，left=0未检查
    • left=n-2, right=n-1终止循环，right=n-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

BinarySearchKeep0(nums[0..n-1], target):
	// 折半查找，保证左右指针不交错
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = 0, n
	while left < right:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			left = mid + 1
		else:
			right = mid

	// post-processing
	if left != len(nums) and nums[left] == target:
		return left

	return -1

• 初始条件：left = 0, right = n，保证n-1可以被正确处理
• 终止情况：left = right
• 指针移动：left = mid + 1, right = mid
• 中点选择对此有影响，指针移动行为非对称，取ceiling则 终止情况还有left = right + 1

• 关键特点

  • left、right循环内不会重合
  • 由于floor的特性，mid可以right任意比较，无需 顾忌和right重合
  • 需要和右邻居、right比较时适合使用

• 终止情况：left = right

  • 循环过程中会保证查找空间至少有2个元素，否则循环 终止
  • 循环终止条件导致退出循环时，可能left=right=n越界

• target位置

  • 若存在target，可能位于mid、left=right
  • 若不存在target，则target位于(left-1, left)
  • 适合访问目标在数组中索引、及其直接右邻居

• 仅二分查找，甚至无需后处理

• 判断nums长度在某些语言中也可以省略

高级版3-原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

BinarySearchNoKeep(nums[0..n-1], target):
	// 折半查找，保证左右指针不交错
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = -1, n-1
	while left < right - 1:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			left = mid
		else:
			right = mid - 1

	// post-processing
	if right >= 0 and nums[right] == target:
		return right

	return -1

• 初始条件：left = -1, right = n-1
• 终止情况：left = right、left = right + 1
• 指针移动：left = mid, right = mid - 1
• 中点选择对此有影响，指针移动行为非对称，取ceiling则 同高级版本2

• 终止条件：left = right、left = right - 1

  • 循环过程中保证查找空间至少有3个元素，否则循环 终止

  • 由于floor特性，必须在left < right - 1时即终止 循环，否则可能死循环

  • 循环终止后，left=right=-1可能越界

• target位置

  • 若存在target，可能位于mid、left=right
  • 若不存在target，则target位于(left, left+1)
  • 适合访问目标在数组中索引、及其直接左邻居

• 此版本仅想实现二分查找必须后处理

  • 终止条件的原因，最后一次right=left + 1时未被检查 即退出循环

  • 可能在任何位置发生，不是端点问题

特点

• 前两个版本比较常用，最后两个版本逻辑类似

• 折半查找时间效率

  • 最坏情况下：$\in \Theta(log n)$
  • 平均情况下仅比最差稍好

• 就依赖键值比较的查找算法而言，折半查找已经是最优算法 ，但是插值算法、散列法等具有更优平均效率

• 减常因子因子法

插值查找

Interpolation Search：查找有序数组，在折半查找的基础上考虑 查找键的值

算法

• 假设数组值是线性递增，即数字值~索引为一条直线，则根据 直线方程，可以估计查找键K在A[l..r]所在的位置

  $$x = l + \left \lfloor \frac {(K-A[l])(r-l)} {A[r] - A[l]} \right \rfloor$$

• 若k == A[x]，则算法停止，否则类似折半查找得到规模更小的 问题

特点

• 即使数组值不是线性递增，也不会影响算法正确性，只是每次 估计查找键位置不够准确，影响算法效率

• 统计考虑

  • 折半插值类似于非参方法，只考虑秩（索引）方向
  • 插值查找类似参数方法，构建了秩（索引）和数组值模型， 但是线性关系基于假设
  • 如果模型错误可能会比折半查找效率更差，即在数据分布 分布偏差较大的情况下非参方法好于参数方法

• 所以是否可以考虑取样方法，先取5个点构建模型，然后估计

• 算法效率

  • 对随机列表，算法比较次数小于$log_2log_n+1$
  • 最差情况，比较次数为线性，没有折半查找稳定
  • Robert Sedgewick的Algorithms中研究表明，对较小文件 折半查找更好，大文件、比较开销大插值查找更好

• 减可变规模

子串匹配

蛮力字符串匹配

算法

• 将pattern对齐文本前m个字符，从左向右匹配相应字符
  • m个字符全部匹配，匹配成功，算法停止
  • 遇到不匹配字符则
• 模式右移1位，然后从模式首个字符开始重复以上匹配
• 在n-m位置无法匹配成功，则无足够匹配字符，算法停止

1
2
3
4
5
6
7
8
9
10
11
12

BruteForceStringMatch(T[0..n-1], P[0..m-1])
	// 蛮力字符串匹配
	// 输入：文本T：n个字符的字符数组
	//       模式：m个字符的字符数组
	// 输出：查找成功返回文本第一个匹配子串中第一个字符位置
	for i = 0 to m-m do
		j = 0
		while j < m and P[j] = T[i+j] do
			j = j + 1
			if j = m
				return i
	return -1

特点

• 最坏情况下，算法比较次数属于$O(nm)$
  • 即在移动模式之前，算法需要做足m次比较
  • 但是一般在自然语言中，算法平均效率比最差好得多
  • 在随机文本中，有线性效率

Horspool算法

算法从右往左匹配，在任意位置匹配不成功时只考虑 同模式最后字符匹配的文本字符c，确定安全移动距离，在 不会错过匹配子串的情况下移动最长距离

• 如果c在模式中出现，则模式移动到其最后c至同文本中c 匹配
• 否则移动模式长度m
• 特别的，如果c只在模式最后字符出现，则也应该移动m

算法

• 对给定长度m的模式及文本中用到的字母表，构造移动表t
• 将模式同文本开始对齐
• 重复以下过程直至发了了匹配子串或模式达到了文本字符外
  • 从模式最后字符开始，比较模式、文本相应字符
  • 若m个字符匹配，停止
  • 遇到不匹配字符c，若为当前文本中和模式最后匹配字符 对齐的字符，将模式移动t(c)个字符

1
2
3
4
5
6
7
8
9
10
11

ShiftTable(P[0..m-1])
	// 用Horspool算法、Boyer-Moore算法填充移动表
	// 输入：模式P[0..m-1]、可能出现字符表
	// 输出：以字符表为为索引的数组Table[0..size-1]
	for i=0 to size-1 do
		Table[i] = m
		// 初始化所有字符对应移动距离为m
	for j=0 to m-2 do
		Table[P[j]] = m - 1 - j
		// 对模式中存在的字符重新计算移动距离
	return Table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

HorspoolMatching(P[0..m-1], T[0..n-1])
	// 实现Horspool字符串匹配算法
	// 输入：模式P[0..m-1]、文本T[0..n-1]
	// 输出：第一个匹配子串最左端字符下标，未匹配返回-1
	Table = ShiftTable(P[0..m-1])
	i = m - 1
	while i <= n-1 do
		k = 0
		while k <= m-1 and P[m-1-k]=T[i-k] do
			k = k+1
		if k == m
			return i-m+1
		else
			i = i+Table[T[i]]
	return -1

特点

• 算法效率

  • 最差情况下模式为相同字符，效率$\in O(nm)$
  • 对随机文本效率$\in O(n)$

• 输入增强

Boyer-Moore算法

• 坏符号移动：模式、文本中相应不匹配字符确定的移动 （不是Horspool中简单根据最后字符确定移动）
• 好后缀移动：模式、文本匹配的后缀确定的移动

算法

• 对给定长度m的模式及文本用到的字母表，构造坏符号移动表t
• 对给定长度m的模式构造后缀移动表
• 将模式与文本开始处对齐
• 重复以下直到找到匹配子串或模式达到文本字符以外
  • 从模式最后字符开始比较模式、文本相应字符
  • 所有m个字符匹配，则停止
  • 若c是不匹配字符，移动坏符号表、后缀移动表决定的 距离较大者

1
2
3
4
5

BadSymbolShift(P[0..m-1])
	// 创建坏符号移动表
	// 输入：模式P[0..m-1]
	// 输出：坏符号移动表

特点

• 算法效率

  • 算法效率最差也是线性的

• 输入增强

KMP算法

算法从左往右匹配，失败时不回溯指针，利用已经得到的 部分匹配结果尽可能将模式滑动一段距离，从模式中间next 字符开始比较

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

KMPShift(P[0..m-1])
	// 计算KMP算法next值
	// 输入：模式P[0..m-1]
	// 输出：模式中各元素next值数组
	i = -1
		// 表示开始比较文本中下个字符
	j = 0
	next[0] = -1
		// 即如果模式首字符都不匹配，比较文本下个字符
	while j < m
		if i == -1 or P[j] == P[i]
			i += 1
			j += 1
			// 当前字符匹配成功，决定下个字符next值
			next[j] = i
		else
			i = next[i]
			// 若当前字符没有匹配成功，不会立即处理下个字符
			// next值，而是反复迭代、查询已匹配部分next值，
			// 以获得最大匹配前缀
	return next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

KMPShiftVal(P[0..m-1])
	// 计算KMP算法next值修正版（考虑next值与当前相等）
	// 输入：模式P[0..m-1]
	// 输出：模式中各元素next_val值数组u
	i = -1
		// 表示开始比较文本中下个字符
	j = 0
	next_val[0] = -1
	while j < m do
		if i == -1 or P[j] == P[i]
			i += 1
			j += 1
			if T[j] != T[i]
				next_val[j] = i
			else
				next_val[j] = next_val[i]
				// 考虑了next值相同时，可以再滑动一次
				// 这里会导致next_val值跳跃
		else
			i = next_val[i]
	return next_val

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

KMPMatching(P[0..m-1], T[0..n-1])
	// 实现KMP字符串匹配算法
	// 输入：模式P[0..m-1]、文本T[0..n-1]
	// 输出：第一个匹配子串最左端字符下标，未匹配返回-1
	i = 0
	j = 0
	while i < m and j < n do
		if i == -1 or P[i] == T[j]
			i += 1
			j += 1
		else
			i = next[i]
	if i >= m
		return j - m + 1
	else
		return -1

特点

• 算法效率

  • 算法时间效率$\in O(m+n)$

• 文本指针不需要回溯，整个匹配过程只需要对文本扫描一次， 对流程处理十分有效，可以边读边匹配

• 输入增强

禁忌搜索

进化算法

进化算法：

• 后设启发式算法：适合多种最优化问题，但不保证找到全局最优

Genetic Algorithm

遗传算法：模拟自然界生物进化过程，采用人工进化的方式对目标 空间进行搜索

• 本质是高效、并行、全局搜索方法
• 能在搜索过程中自动获取、积累有关搜索空间的知识，并自适应 的控制搜索过程以求的最佳解

思想

• 将问题域中可能解看作是染色体，将其编码为符号串的形式
• 对染色体群体反复进行基于遗传学的操作：选择、交叉、变异
• 根据预定目标适应度函数对每个个体进行评价，不断得到更优 群体，从中全局并行搜索得到优化群体中最优个体

实体

• population：群体，GA的遗传搜索空间
• individual：个体，搜索空间中可能解
• chromosome：染色体，个体特征代表
  • 由若干段基因组成
  • GA中基本操作对象
• gene：基因
  • 染色体片段
• fitness：适应度，个体对环境的适应程度

基本操作

• selection：选择，根据个体适应度在群体中按照一定概率 选择个体作为父本

  • 适应度大个体被选择概率高
  • 体现了适者生存、优胜劣汰的进化规则

• crossover：交叉，将父本个体按照一定概率随机交换基因 形成新个体

• mutate：变异，按照一定概率随机改变某个体基因值

串编码方式

• 把问题的各种参数用二进串进行编码构成子串
• 把子串拼接成染色体

  • 串长度、编码方式对算法收敛影响极大

二进制编码方式

二进制法：使用二进制染色体表示所有特征

• 优点

  • 编码、解码操作简单
  • 交叉、变异等遗传操作便于实现
  • 符合最小字符集编码原则
  • 利于模式定理对算法理论分析

• 缺点

  • 连续函数离散化存在误差，染色体长度短时达不到精度 要求，较长时解码难度大、搜索空间增大
  • 对连续函数优化问题，随机性使得其局部搜索能力较差， 接近最优值时不稳定

浮点编码

浮点法：个体的每个基因值用某一范围内的一个浮点数表示

• 必须保证基因之在给定区间限制范围内

  • 交叉、变异等遗传算子结果也必须在限制范围内

• 优点

  • 适用于在遗传算法中表示范围较大的数
  • 精度较高
  • 便于较大空间的遗传搜索
  • 改善了遗传算法的计算复杂性，提高了运算效率
  • 便于遗传算法与经典优化方法的混合使用
  • 便于设计针对问题的专门知识的知识型遗传算子
  • 便于处理复杂的决策变量约束条件

符号编码法

符号法：个体染色体编码串基因值取自无意义字符集

• 优点
  • 符合有意义积木块编码原则
  • 方便利用所求解问题的专门知识
  • 访问GA和相关近似算法的混合使用

Fitness Function

适应度/对象函数

• 一般可以把问题模型函数作为对象函数

• 过程

  • 解码个体，得到个体表现型
  • 由个体表现型计算个体目标函数值
  • 根据最优化问题类型，由目标函数值按一定转换规则求出 个体适应度

操作

选择函数

• Roulette Wheel Selection：轮盘赌选择，个体进入下一代 概率为其适应度与整个种群适应度之比

  • 放回式随机抽样
  • 选择误差较大

• Stochastic Tournament：随机竞争选择，每次按轮盘赌选择 一对个体，选择适应度较高者，重复直到选满

• 最佳保留选择：按轮盘赌选择方法执行遗传算法选择操作，然后 t将当前群体中适应度最高的个体结构完整地复制到下一代群体中

• Excepted Value Selection：无回放随机选择，根据每个个体 在下一代群体中的生存期望来进行随机选择运算

  • 计算群体中每个个体在下一代群体中的生存期望数目N
  • 若体被选中参与交叉运算，则它在下一代中的生存期望数目 减去0.5，否则在下一代中的生存期望数目减去1.0
  • 随着选择过程的进行，当个体的生存期望数目小于0时，则 该个体就不再有机会被选中。

• 确定式选择：按照一种确定的方式来进行选择操作

  • 计算群体中各个体在下一代群体中的期望生存数目N
  • 用N的整数部分确定个体在下一代群体中的生存数目
  • 用N的小数部分对个体进行降序排列，顺序取前M个个体加入 到下一代群体
  • 完全确定出下一代群体中Ｍ个个体

• 无回放余数随机选择

  • 可确保适应度比平均适应度大的一些个体能够被遗传到 下一代群体中
  • 选择误差比较小

• 均匀排序：对群体中的所有个体按期适应度大小进行排序，基于 这个排序来分配各个个体被选中的概率

• 最佳保存策略：当前群体中适应度最高的个体不参与交叉运算 和变异运算，而是用它来代替掉本代群体中经过交叉、变异等 操作后所产生的适应度最低的个体

• 随机联赛选择：每次选取几个个体中适应度最高个体遗传到 下一代群体中。

• 排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高 群体的多样性

Cross Over

• One-point Crossover：单点交叉，在个体编码串中只随机 设置一个交叉点，然后再该点相互交换两个配对个体的部分 染色体

• Two-point Crossover：两点交叉，在个体编码串中随机设置 两个交叉点，然后再进行部分基因交换

• Multi-point Crossover：多点交叉

• Uniform Crossover：均匀交叉/一致交叉，两个配对个体的 每个基因座上的基因都以相同的交叉概率进行交换，从而形成 两个新个体

• Arithmetic Crossover：算术交叉，由两个个体的线性组合 而产生出两个新的个体

  • 操作对象一般是由浮点数编码表示的个体

Mutation

• Simple Mutation：基本位变异，对个体编码串中以变异概率 、随机指定的某一位或某几位仅因座上的值做变异运算

• Uniform Mutation：均匀变异，用符合某一范围内均匀分布 的随机数，以较小的概率来替换个体编码串中各个基因座上原有 基因值

  • 适用于在算法的初级运行阶段

• Boundary Mutation：边界变异，随机的取基因座上的两个 对应边界基因值之一去替代原有基因值

  • 适用于最优点位于或接近于可行解的边界时的一类问题

• 非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果 作为变异后的新基因值

  • 对每个基因值都以相同的概率进行变异运算之后，相当于 整个解向量在解空间中作了一次轻微的变动

• 高斯近似变异：进行变异操作时用符号均值为P、方差$P^2$的 正态分布的一个随机数来替换原有的基因值

GA超参设置

• 群体大小$n$：过小难以求出最优解，过大难收敛，一般取 $n = 30 ~ 160$

• 交叉概率$P_c$：太小难以前向搜索，太大容易破坏高适应 值结构，一般取$P_c = 0.25 ~ 0.75$

• 变异概率$P_m$：太小难以产生新结构，太大则变为单纯 随机搜索，一般取$P_m = 0.01 ~ 0.2$

算法

1. 随机初始化种群
2. 估初始种群：为种群每个个体计算适应值、排序
3. 若没有达到预定演化数，则继续，否则结束算法
4. 选择父体
   • 杂交：得到新个体
   • 变异：对新个体变异
5. 计算新个体适应值，把适应值排名插入种群，淘汰最后个体
6. 重复3

Differential Evolution

差分进化算法：

Particle Swarm Optimization

粒子群/微粒群算法：

Simulated Annealing Algorithm

模拟退火算法

• 来源于固体退火原理

  • 将固体加热至充分高，固体内部粒子随之变为无序状，内能 增加
  • 再让固体徐徐冷却，内部例子随之有序
  • 到达常温状态时，内能减为最小

• 用固体退火模拟组合优化问题

  • 目标函数值f视为内能E，控制参数t视为温度T
  • 由初始解i、控制参数初值t开始，对当前解重复 产生新解->计算目标函数增量->接受或舍弃的迭代，并 逐步衰减t值
  • 算法终止时，当前解即为所得近似最优解

• 退火过程由Cooling Schedule控制，包括控制参数初值t、衰减 因子$\Delta t$、迭代次数L、停止条件S

算法

• 初始化：初始温度$t_0$（充分大）、初始解$i_0$、迭代次数L
• 产生新解$i_1$，计算目标函数增量$\Delta f=f(i_1)-f(i)$
• 若$\Delta f<0$则接受$i_1$作为新解，否则以概率 $\exp^{\Delta f/f(i_0)}$接受$i_1$作为新解
• 若满足终止条件则算法结束
  • 若干次新解都不被接受：当前解“能量”低
  • 迭代次数达到上限
• 否则减小温度为$t_1$继续迭代

说明

• 解生成器：应该可以通过简单变换即可产生新解，便于减少每次 迭代计算新解耗时

  • 比如对新解全部、部分元素进行置换、互换等
  • 需要注意的是，这决定了新解的领域结构，对冷却的进度表 选取有影响

• 新解是否被接受采用的是Metropolis准则

模拟退火算法性质

• 与初值无关
• 具有渐进收敛性
• 具有并行性
• 在理论上被证明是以概率1收敛于全局最优解的算法
• 能够跳出局部最优解

应用

• VLSI：目前退火模拟算法的应用实例，几乎可以完成所有VLSI 设计工作
• 神经网络：模拟退火算法能够跳出局部最优解
• 图像处理：用于进行图像恢复工作
• 其他问题：还可以用于其他各种组合优化问题

数值随机化算法

数值化随机算法：常用于数值问题求解，往往得到的是近似解

• 近似解的精度随计算时间、采样数量增加不断提高
• 很多情况下计算问题的精确解不可能、无必要，数值化随机算法 可以得到较好的解

随机投点法

随机投点法：在给定范围内生成均匀分布随机数模拟随机投点

• 计算$\pi$值：在正方形、内切圆中随机撒点，计算圆内、 正方形内点数量之比

• 计算黎曼积分：在包括积分区域单位矩形内随机投点，计算 积分区域、矩形区域点数量之比

平均值法

平均值法：结合随机数分布、目标问题构造统计量，估计目标问题

计算黎曼积分

• 假设独立同分布随机变量${\eta_i}$在$[a, b]$中服从分布 $f(x)$、待积函数为$g(x)$

• 记$g^{*}(x) = \frac {g(x)} {f(x)}$，则有

  $$\begin{align*} E(g^{*}(\eta)) & = \int_a^b g^{*}f(x) dx \\ & = \int_a^b g(x) dx = I \end{align*}$$

• 由强大数定理

  $$P_r(\lim_{x \rightarrow \infty} \frac 1 n \sum_{i=1}^n g^{*}(\eta_i) = I) = 1$$

  选择$\bar I = \frac 1 n \sum_{i=1}^n g^{*}(\eta_i)$， 则$\bar I$依概率收敛为$I$

• 选择抽样方法简单的概率密度函数$f(x)$满足

  $$\left \{ \begin{array}{l} f(x) \neq 0, & g(x) \neq 0, a \leq x \leq b \\ \int_a^b f(x) dx = 1 \end{array} \right.$$

  可以取$f(x)$为均匀分布

  $$f(x) = \left \{ \begin{array}{l} \frac 1 {b-a}, & a \leq x \leq b \\ 0, & x < a, x > b \end{array} \right.$$

• 则积分

  $$I = \int_a^b g(x)dx = (b-a) \int_a^b g(x) \frac 1 {b-a}dx$$

  取均值

  $$\bar I = \frac {b-a} n \sum_{i=1}^n g(x_i)$$

  可作为求分I的近似值

解非线性方程组

• 线性化方法、求函数极小值方法有时会遇到麻烦，甚至使方法 失效而不能获得近似解
• 随机化方法相较而言要耗费较多时间，但设计简单、易于实现
• 对于精度要求较高的问题，随机化方法可以提供一个较好的初值

步骤

• 构造目标函数

  $$\Phi(x) = \sum f_i^2(x)$$

  则目标函数的极小值点即为所求非线性方程组的一组解

• 随机选择点$x_0$作为出发点，不断随机生成搜索方向， 迭代为使得目标函数值下降的搜索点

  • 一般以目标函数变化幅度、迭代轮数作为终止条件
  • 搜索方向为随机生成，迭代步长比例每轮缩小指定幅度

• 真正的随机次梯度下降

Monte Carol Method

蒙特卡洛算法：一定能给出问题解，但未必正确

• 要求在有限时间、采样内必须给出解，解未必正确
• 求得正确解的概率依赖于算法所用时间，算法所用时间越多， 得到正确解概率越高
• 无法有效判断得到的解是否肯定正确

Las Vegas Method

拉斯维加斯算法：找到的解一定是正确解，但是可能找不到解

• 找到正确解的概率随着计算所用时间增加而提高
• 用同一拉斯维加斯算法反复对实例求解多次，可使得求解失效 概率任意小

Sherwood Method

舍伍德算法：能求得问题的一个解，所求得得解总是正确的

• 确定性算法在最好情况、平均情况下计算复杂度有较大差别， 在确定性算法中引入随机性将其改造成舍伍德算法，消除、减少 问题的好坏实例间差别

• 精髓不是改进算法在最坏情形下的行为，而是设法消除最坏情形 与特定问题实例的关联性

思想

• 问题输入规模为n时，算法A所需的平均时间为

  $$\bar t_A(n) = \sum_{x \in X_n} t_A(x) / |X_n|$$

  • $X_n$：算法A输入规模为n的实例全体
  • $t_A(x)$：输入实例为x时所需的计算时间

  显然存在$x \in X_n, t_A(x) >> \bar t_A(x)$

• 希望获得随机化算法B，使得对问题的输入规模为n的每个实例 $x \in X_n$均有$t_B(x) = \bar t_A(x) + s(n)$

  • 对具体实例，存在$x \in X_n$，算法B需要时间超过 $\bar t_A(x) + s(n)$，但这是由于算法所做的概率引起， 与具体实例无关

  • 算法B关于规模为n的随机实例平均时间为

    $\begin{align*} \bar t_B(n) & = \sum_{x \in X_n} t_B(x) / (X_n) \\ & = \bar t_A(n) + s(n) \end{align*}$K

    当$s(n)$与$\bar t_A(n)$相比可以忽略时，舍伍德算法 可以获得较好平均性能

todo

Hashing Table

• 哈希表/散列表：可根据哈希值直接访问的数据结构

• 原理：以哈希值做为地址，缩小搜索空间、提高查找效率

  • 使用哈希函数为每个键计算哈希值，得到位于 $0, \cdots, m-1$之间整数
  • 按照哈希值把键分布在$H[0, \cdots, m-1]$哈希表中
  • 查找匹配键时，以查找键哈希值作为起点在哈希表中 搜索

• 应选择合适的哈希函数、哈希表长度，尽量把键尽量均分在 哈希表中

  • 哈希函数$hash$：参见math_algebra/#todo
    • 对闭散列：减少冲突
    • 对开散列：避免数据集中
  • 散列表长度$m$：常为质数（方便双散列）

Load Factor

负载因子：$\alpha = \frac {noempty} {m}$

• $m$：哈希表中slots数量（长度）（哈希桶数量）
• $noempty$：非空数量

• 闭散列：负载因子反映哈希表冲突可能性、查找效率

  • 负载因子过小：冲突可能性小，查找效率高，但浪费空间
  • 负载因子过大：冲突可能性大，查找效率低，空间利用率高
  • 负载因子取值最大为1
  • 应适当平衡负载因子，负载因子接近1时重散列，避免冲突 过多影响查找效率

  • Java中HashMap初始负载值为0.75

• 开散列：负载因子反映查找效率

  • 但应该无法反映冲突可能性（也无必要）
    • 开散列往往被用于应对大规模数据，冲突总是存在
    • 查找效率更多取决于数据（哈希值）偏倚程度
  • 负载因子可以大于1

应用

• 字典/映射实现：cs_algorithm/data_structure/set

Open Addressing

闭散列/开放寻址：所有键存储在散列表本身中，不扩展存储空间

• 哈希表$m$至少要和哈希键数量$n$一样大

• 冲突问题解决：根据一定规则计算下个地址

• cluster：聚合，散列表接近满时，一序列连续单元格被占据

  • 线性探查性能恶化，操作效率降低
  • 聚合越来的越大时，新元素插入聚类可能性增加
  • 聚合可能被新插入元素连接，导致更大程度聚合

增量类型

增量类型：碰撞发生后，根据一定规则对原哈希值修正

• $d_i = i$：linear probing，线性探查
• $d_i = i^2, -i^2$：quadratic probing，二次探查
• $d_i = 伪随机数$：伪随机探查
• $d_i = i hash_2(K), i=0,1,2,\cdots$：double hashing* ，再散列法

• 再散列法说明：为保证哈希表中每个位置被探查，增量$s(K)$ 必须互质
  • $m$为质数时自动满足
  • 文献推荐：$s(K) = m - 2 - K mod (m-2)$
  • 对较小散列：$s(K) = 8 - (K mod 8)$
  • 对较大散列：$s(K) = K mod 97 + 1$

操作

• 插入：依次检查哈希值$h(K)$、探查目标序列，直至找到空 单元格放置键

• 查找：给定查找键K，计算哈希值$h(K)$、探查目标序列，比较 K和单元格中键值

  • 若查找到匹配键，查找成功
  • 遇到空单元格，查找失败

• 删除：延迟删除，用特殊符号标记曾经被占用过、现被删除 的位置

  • 不能直接删除，否则的中间出现空单元格，影响查找正确性

算法效率

• 成功查找访问次数： $S \approx \frac 1 2 (1+\frac 1 {(1-\alpha)})$

• 失败查找访问次数： $U \approx \frac 1 2 [1+\frac 1 {(1-\alpha)^2}]$

• 简化版本近似结论（散列规模越大，近似结论越正确）
• 无法避免散列表趋满时性能恶化
• 再哈希法数学分析困难，经验表明优秀的散列函数（两个）， 性能较线性探查好

Multi Hashing

多重哈希：使用一组哈希函数$h_0,\cdots,h_n$依次计算哈希值， 确定插入、查找地址

• 类似增量类型方法，仅各次地址独立使用哈希函数计算

增大空间

Rehashing

重散列：扫描当前表，将所有键重新放置在更大的表中

• 散列表趋满时唯一解决办法

Overflow Area

建立公共溢出区：将哈希表分为基本表、溢出表两部分

• 将发生冲突的元素都放入溢出区
• 基本表中可以考虑为为每个哈希值设置多个slots
  • 即基本表直接存储哈希桶

Chaining

开散列/分离链：哈希表作为目录，使用额外数据空间组织哈希键

拉链法/分桶法

拉链法/分桶法：哈希表作为目录项存储指向hash桶的指针，hash桶 中存储哈希键

• 目录项表：顺序表，连续存储空间

  • 可以通过hash值在常数时间内定位：一般其索引位置就是 hash值
  • 目录项越多，数据分布相对越稀疏、碰撞概率越小、效率 越高

• hash桶：存储具有相同哈希值元素的顺序表

  • 目录项存储chain为顺序表：每个链即为hash桶
  • 目录项存储chain为顺序表链：链中每个顺序表为hash桶
    • 即每个目录项对应多个hash值，链接多个hash桶

操作

• 查找
  • 对查找键K，使用同样散列函数计算键散的函数值$h(K)$
  • 遍历相应单元格附着链表，查找是否存在键K
• 插入：计算键对应桶，在链表尾部添加键即可
• 删除：查找需要删除的键，从链表中移除即可

算法效率

• 效率取决于链表长度，而链表长度取决于字典、散列表长度 和散列函数质量

  • 成功查找需要检查指针次数$S = 1 + \alpha / 2$
  • 不成功查找需要检查指针次数$U = \alpha$
  • 计算散列函数值是常数时间操作
  • 若n和m大致相等，平均情况下$\in \Theta(1)$

• 算法查找的高效是以额外空间为代价的

Perfect Hashing

完美哈希：采用两级全域哈希，目录项链接独立哈希表的拉链哈希表

• 二级哈希表开头部分存储哈希表元信息

  • $m = n^2$：哈希表槽数，$n$为映射至该槽元素数量 （此时由全域哈希性质：冲突次数期望小于0.5）
  • $a, b$：全域哈希参数

• 复杂度

  • 时间复杂度：最坏情况下查找为$O(1)$
  • 空间复杂度：期望空间为线性 $E(\sum_{i=1}^{m-1} \theta(n_i^2) = \theta(n)$

• 完美哈希没有冲突的概率至少为0.5
• 全域哈希参见math_algebra/hash_funcs

Dynamic Hashing

动态hash：在hash表中元素增加同时，动态调整hash桶数目

• 在原hash表基础上进行动态桶扩展
• 不需要遍历表元素重复执行插入操作
• 开散列法在大规模、在线数据的扩展

多hash表

多hash表：通过建立多个hash表的方式扩展原hash表

• 思想、实现简单
• 占用空间大，数据分布偏斜程度较大时，桶利用率不高

实现

操作时需要考虑多个hash表

• 插入

  • 若存在hash相应桶中存在空闲区域，直接插入
  • 否则分裂，新建hash表，插入元素至空闲区域

• 查找：需要查找所有hash表相应桶才能确定

  • 当表中元素较多时，可以考虑并行执行查找操作

• 删除操作：若删除元素导致某hash表空，可考虑删除该表

可扩展动态hash

可扩展动态hash：只分裂将要溢出的桶，使用目录项作为索引

• 多个目录项可能指向同一个桶
• 分裂时代价较小
  • 翻倍目录项替代翻倍整个hash表
  • 每次只分裂将要溢出桶
  • 只需要进行局部重散列，重分布需要分裂的桶
• 目录指数级增长
  • 数据分布不均时，会使得目录项很大

插入

• D：全局位深度，hash值截断长度，为局部桶深度最大值
• L_i：桶局部深度，等于指向其目录项数目

• 若对应桶存在空闲位，则直接插入

  

• 否则分裂桶：分裂后两桶局部深度加1

  

  • 若分裂桶局部深度不大于全局位深度

    • 创建新桶
    • 重散列原始桶中数据
    • 更新目录项中对应指针：分别指向分裂后桶

  • 若分类桶局部深度大于全局位深度

    • 更新全局位深度
    • 目录项翻倍
    • 创建新桶
    • 重散列原始桶中数据
    • 更新目录项中对应指针
      • （新增）无关目录项仍然指向对应桶
      • 相关目录项指向分别指向分裂后桶

查找

• 计算原始hash值
• 按照全局位深度截断
• 寻找相应目录项，找到对应桶，在桶中进行比较、查找

删除

• 计算原始hash值
• 按照全局位深度截断
• 寻找相应目录项，找到对应桶，在桶中进行比较、删除
  • 若删除后发现桶为空，考虑与其兄弟桶合并，并使局部深度 减1

线性散列

线性散列：按次序分裂桶，保证整个建表过程类似完全二叉树

• 整个哈希表建表过程始终保持为完全二叉树

  • 每次分裂的桶是完全二叉树编号最小的叶子节点
  • 分裂前后桶间均为有序

• 相较于可扩展散列

  • 无需存放数据桶指针的专门目录项，节省空间
  • 能更自然的处理数据桶满的情况
  • 允许更灵活的选择桶分裂时机
  • 但若数据散列后分布不均，则问题可能比可扩散散列严重

• 实现相较而言更复杂

桶分裂

• N：hash表中初始桶数目，应为2的幂次
• d = log_2N：表示桶数目需要位数
• level：分裂轮数，初始值为0，则每轮初始桶数为 $N * 2^{level}$
• Next：下次要发生分裂的桶编号

• 每次同分裂条件可以灵活选择

  • 设置桶填充因子，桶中记录数达到该值时进行分裂
  • 桶满时发生分裂

• 每次发生的分裂的桶总是由Next决定

  • 与当前被插入的桶溢出无关，可引入溢出页处理桶溢出
  • 每次只分裂Next指向的桶，桶分裂后Next += 1
  • 后续产生映像桶总是位于上次产生映像桶之后

• “轮转分裂进化”：各桶轮流进行分裂，一轮分裂完成后进入下轮 分裂

查找

• 根据N、level计算当前d值，截取原始hash值

• 若hash值位于Next、N之间，说明该轮对应桶还未分裂， 直接在桶中查找

• 若hash值小于Next，说明该轮对应桶已经分裂，hash值向前 多取一位，在对应桶中查找

删除

• 删除操作是插入操作的逆操作

• 若删除元素后溢出块为空，可直接释放
• 若删除元素后某个桶元素为空，Next -= 1
  • 当Next减少到0，且最后桶也是空时，Next = N/2 - 1 ，同时level -= 1

1`