算法分析与设计复习

第二章 算法初步

插入排序

arr = []
for i in range(1, n):
	key = arr[i]
	j = i - 1
	while j and arr[j] > key:
		arr[j] = arr[j-1]
		j -= 1
	arr[j+1] = key

循环不变式

比如插入排序，每次循环从数组 A 中取出第 j 个元素插入有序区 A[1 .. j-1]，然后递增 j。这样A[1 .. j-1] 的有序性始终得到保持，这就是所谓的“循环不变”了。

要用循环不变式证明一个循环的正确性，通常需要证明以下三点：

• 初始化：循环的第一次迭代之前，它为真。
• 保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
• 终止：在循环终止时仍为真，不变式为我们提供一个有用的性质，该性质有助千证明算法是正确的

例：用循环不变式证明插入排序算法的正确性

循环不变式：在每次循环 i 开始前，数组的 [0, …, i-1] 都是有序的

1. 初始化：在第一次循环之前，i=1，数组 [0,…,i-1] 只有一个元素，所以是有序的
2. 保持：在每次迭代过程中，假设 [1…i-1]是已经排好序的序列，待排序的元素 A[i] 依次与A[i-1]、A[i-2] 进行比较，如果 A[i-1] 等大于 A[i]，则依次将其向右移动一位 A[j+1]<—A[j]，当遇到开始小于 A[i] 的元素时，则 A[i] 找到了合适的插入位置，插入之后，整个序列又是排好序的了。
3. 当 i=n+1 时，循环结束，此时A[1…n]中已经有n个元素，且已经排好序。

复杂性分析

对于插入排序，我们可以得到每条代码执行次数如上图，所以总运行时间为：

当数组基本有序时候，会出现最佳情况 $t_j=1$，总运行时间为

可以表示为 $T(n)=an+b$，是关于 n 的线性函数。但是当数组反向排序时候出现最坏情况，每次都需要和 A[0,…,j-1] 对比，所以这时候 $t_j=j$，变成二次函数。

具体证明如书p15。

一般来说平均时间复杂度和最坏时间复杂度一样坏，最坏情况时间复杂度用 $\Theta$ 来表示，插入排序就是 $\Theta(n^2)$ 。

归并排序及其时间复杂度

def MergeSort(arr, p, r):
	if p < r:
		q = (q + r) / 2
		MergeSort(arr, p, q)
		MergeSort(arr, q+1, r)
		Merge(arr, p, q, r)
def Merge(arr, p, q, r):
	n1 = q - p + 1
	n2 = r - q
	l = arr[p:q+1]
	l.append(INF)
	r = arr[q+1:r+1]
	r.append(INF)
	i = j = 0
	for k in range(p, r+1):
		if l[i] > r[j]:
			arr[k] = r[j]
			j += 1
		else:
			arr[k] = l[i]
			i += 1

原本的代码需要判断 i 和 j 是否超过了边界，现在用哨兵 INF 就能解决这个问题。

每个规模为 n 的问题可以被分解为两个规模为 $\frac{n}{2}$ 的子问题，加上合并的时间复杂度 $\Theta(n)$ ，就可以得到归并排序的时间递推式。具体 T(n) 怎么推出时间复杂度为 $O(nlogn)$ 在后面说。

课后题

31 41 59 26 41 58
31 41 59 26 41 58
31 41 58 26 41 58
26 31 41 58 41 58
26 31 41 41 58 58
26 31 41 41 58 58

def linear_find(A, v):
	for i, x in enumerate(A):
		if v == x: return i
	return -1

循环不变式：每次循环 i 前，数组 A[0, .. i-1] 不含元素 v

1. 初始：第一次循环，循环不变式为空，肯定不含 v
2. 维护：之后每一次循环，如果新元素等于 v 就返回退出了；如果不等于 v 才加入循环不变式，所以 A[0, .. k-1] 肯定不含元素 v
3. 结束：当 i=n+1 时候循环结束，此时循环内 n 个元素都不为 v，满足循环不变式。如果含元素 v 则在结束前退出。

def SelectSort(arr):
	n = len(arr)
	for i in range(0, n):
		min_val = INF
		min_idx = -1
		for i in range(i+1, n):
			if arr[i] < min_val:
				min_val = arr[i]
				min_idx = i
		swap(arr[i], arr[idx])

• 最坏情况 $O(n^2)$
• 最好情况 $O(n)$

循环不变式：每次循环 i 前，数组 A[0, ..., i-1] 递增

1. 初始：第一次循环前，循环不变式为空，所以满足条件
2. 维护：每一次循环 k 之后，会从数组 A[k-1:n] 中挑选最小的元素，也就是数组第 k 小的元素插入，保证了依旧是单调递增
3. 结束：当 i=n+1 时候循环结束，数组内元素依次为第一小，第二小，…，依次递增，满足循环不变式

def Merge(arr, p, q, r): 
	n1 = q - p + 1 
	n2 = r - q 
	l = arr[p:q+1]
	r = arr[q+1:r+1]
	i = j = 0
	k = p
	while i < n1 and j < n2:
		if l[i] > r[j]: 
			arr[k] = r[j] 
			j += 1 
		else: 
			arr[k] = l[i] 
			i += 1
		k += 1
	while i < n1:
		arr[k] = l[i]
		k += 1
		i += 1
	while j < n2:
		arr[k] = r[j]
		k += 1
		j += 1

不行，因为查找的时间降下来了，但是还有移动元素的时间。

第三章 函数增长率

不同渐进符号

和式界的证明方法

等差和

等比和

调和级数

放缩法

所以紧确界是 $\Theta(n\log n)$ 。

课后题

根据多项式展开定理：

经过放缩：

所以：

对于等式 2，找不到一个 c 可以使 $2^{2n} \le c*2^n$ 所以不成立。

3.2-3 和 3.2-5 太偏数学了肯定不考。

第四章 递归关系式

代入法

对于之前归并排序的例子，我们假设它的解是 $T \left(n\right) = O \left( n lgn \right)$ ，即我们需要证明 $T\left( n \right) \le c_1nlgn$。

根据数学归纳法，首先我们要确定当 n 比较小时该猜测成立。当 $n=1$ 时，$T\left(1\right) = \Theta \left(1 \right) = d_1$  ，其中 $d_1$ 是某个大于 0 的常数。根据猜测，我们希望 $T\left(1\right) \le c_1 lg1 = 0$ ，可是，无论怎样取 c ，该式都不可能成立，因为 $T\left(1\right) = d_1$ 必然大于 0。数学归纳法还没开始就失败了。不过不必担心，这只是一个 $lg1 = 0$ 导致的特殊情况，我们完全可以把数学归纳法的初始状态放在 $n \gt 1$ 的位置，同时不影响数学归纳法的结果。因为我们只关心当 n 足够大时 $T\left(n\right)$  的渐进性质，而不关心初始阶段。

现在令 n=2 ，则 $T\left(2\right) = 2T\left(1\right) + d_2 = 2d_1 + d_2$ ，我们希望 $T\left( 2 \right) \le c_12lg2$ 成立，化简后得 $c_1 \ge d_1 + d_2/2$ ，由于 $d_1$ 和 $d_2$ 是常数，因此这样的 $c_1$ 是存在的，初始情况成立。

接下来，数学归纳法需要假设解在 $n/2$ 处成立，即 $T\left( \frac{n}{2} \right) \le c_1 \frac{n}{2} lg\frac{n}{2} = \frac{1}{2}c_1n\left(lgn - 1\right)$ 成立。然后我们来证明 $T\left( n \right) \le c_1nlgn$ 也成立。

同理只需要证明 $T \left(n\right) = \Omega \left( n lgn \right)$，就可以得证 $T \left(n\right) = \Theta \left( n lgn \right)$

递归树

步骤：

1. 把递归式中分成递归部分 $T(\frac{n}{2})$ $2T(\frac{n}{4})$ 和每层的处理时间 $O(n)$
2. 递归树每一层都按照递归部分的规则，把上一层瓜分；第一层瓜分的是 $O(n)$
3. 统计每一层的总耗时，最后累加
4. 通过放缩得到最后时间复杂度

主定理

简单的理解：

1. 若 f(n) 增长较慢（情况 1），则递归部分占主导。
2. 若 f(n) 和递归增长相等（情况 2），需额外乘以 log n。
3. 若 f(n) 增长较快且满足平衡条件，则非递归部分占主导。

最大子数组

最大子数组的三种情况：1 在左半边，2 在右半边，3 横跨（从 mid 向两边扩展即可，线性的）

def FindMaxSubarray(arr, l, r):
	if l == r:
		return l, r, arr[l]
	else:
		mid = (l + r) / 2
		left_l, left_r, left_sum = FindMaxSubarray(arr, l, mid)
		right_l, right_r, right_sum = FindMaxSubarray(arr, mid+1, r)
		mid_l, mid_r, mid_sum = FindMaxCross(arr, l, mid, r)
		return ...

def FindMaxCross(arr, l, mid, r):
	left_max = -INF
	right_max = -INF
	sum = 0
	for i in range(mid, l, -1):
		sum += arr[i]
		if sum > left_max:
			left_max = sum
			max_left = i
	sum = 0
	for i in range(mid+1, r):
		sum += arr[i]
		if sum > right_sum:
			right_sum = sum
			max_right = i
	return max_left, max_right, left_max+right_max

FindMaxCross 时间复杂度是 $O(n)$，每次都分成两个子任务，所以递推式微 $T(n)=2T(n/2)+ \Theta(n)$，时间复杂度为 $O(n\lg n)$。

Stranssen 矩阵乘法

给定两个 $n \times n$ 矩阵 A,B，计算：

• 三重循环
• 每个 $C_{ij}$ 需要 n 次乘法
• 一共 $n^2$ 个元素

假设 n 是 2 的幂（不是也能 padding）。

把矩阵分成四个 $\frac{n}{2} \times \frac{n}{2}$ 子矩阵：

普通分治乘法：

递推式是 $T(n)=8T(n/2)+Θ(n2)$ 还是没有改进，Stranssen 的思路是：矩阵加减法是 $O(n^2)$，比乘法便宜，用加法代替乘法。

就能得到：

所以只需要 7 次矩阵乘法加上若干次矩阵加减法，$T(n) = 7T(n/2) + \Theta(n^2)$，根据主定理递推部分时间复杂度比较大，所以为 $\Theta(n^{log_2^7})$。

课后题

出现 n 不是 2 的幂的情况，只需要填充 0 即可。Strassen 算法会把规模为 n 的矩阵分裂为 4 个 规模为 n/2 的子矩阵，进行 7 次乘法和若干次加法，所以递推式为 $T(n)=7T(\frac{n}{2})+O(n)$，根据主定理，时间复杂度为 $O(n^{\lg7})$。

既然 Strassen 算法把规模为 n 的矩阵分裂为 4 个 规模为 n/2 的子矩阵，进行 7 次乘法和若干次加法，递推式写为 $T(n)=7T(\frac{n}{2})+O(n)$，那可以把第一种方法写为 $T(n)=143640T(\frac{n}{70})$，根据主定理得到 $n^{log_{70}^{143640}} \approx n^{2.7951284873613815}$。其他方法同理，和 $\log_2^7$ 对比即可。

猜测：T(n) >= c · n · lgn

证明：n = 1 为递归式基本情况，T(1) = 2T(⌊n/2⌋) + n = 1 。当 n >= 2 时，有 T(n) = 2T(⌊n/2⌋) + n >= 2 · c · ( ⌊n/2⌋ · lg⌊n/2⌋ ) + n >= ？，我的思路到这就卡着了，因为向下取整的符号会让左边 <= 右边，让接下去的推导无法成立，。如果这里是向上取整的符号的话，就可以推出 2 · c · ( ⌈n/2⌉ · lg⌈n/2⌉ ) + n >= c · n · (lgn - 1)+ n =  c · n · lgn 。

看来是要换猜想了。加上些常数如何？参考了别人的解法，新猜测：$T(n) \ge c(n+2)\lg(n+2)$

证明：还是一样，n = 1 为递归式的基本情况，T(1) = 2T(⌊n/2⌋) + n = 1 。当 n >= 2 时，T(n) = 2T(⌊n/2⌋) + n >= 2c · ((⌊n/2⌋ + 2) · (lg⌊n/2⌋ + 2) + n >= 2c · ((n/2 - 1 + 2) · (lg(n/2)  - 1 + 2) + n = 2c · ((n/2 + 1) · lgn) + n = c · (n + 2) · lgn + n >= c · n · lgn ，其中存在 c > 0，使得最后一步推导成立，所以 T(n) = Ω( n·lgn )。

证法类似 4.3-3，如果发现上界/下界整不出来，可能是猜测太紧了，可以加减常数。

不行，$n^{log_b^a}=n^2$ 但是 $n^2\lg n$ 并不是多项式大于 $n^2$ 。

第六章 堆排序

Heapify

堆的维护从上到下，时间复杂度为 $O(\lg n)$ ，就是二叉堆的高。

def MaxHeapify(arr, i):
	l = i.left
	r = i.right
	if l <= size and arr[l] > arr[i]: largest = l
	elif r <= size and arr[r] > arr[i]: largest = r
	else: largest = i
	
	if largest != i:
		swap(arr[i], arr[largest])
		MaxHeapify(arr, largest)

非递归的 MaxHeapify 用 while True 即可，每次 i = largest。

BuildHeap

由于数组 [n/2, …, n] 都是叶节点，叶节点可以看作一个元素的堆，所以建堆时候，只需要维护 [1, …, n/2] 的非叶节点就好。

def BuildHeap(arr):
	for i in range(n/2, 1, -1):
		MaxHeapify(arr, i)

每次调用 MaxHeapify 时间复杂度是 $O(\lg n)$，需要调用 $O(n)$ 次，所以时间复杂度为 $O(n\lg n)$。

HeapSort

不断把堆顶（最大元素）放到队尾，并且堆大小减一。

def HeapSort(arr):
	BuildHeap(arr)
	for i in range(arr.size):
		swap(arr[1], arr[-1])
		arr.size -= 1
		MaxHeapify(arr, 1)

优先队列

假设你有一组数据，每个元素都有一个优先级，你需要反复做两件事：

1. 插入新元素
2. 快速找到并删除当前优先级最高（或最低）的元素

因为堆的插入只需要对插入位置向上进行维护，树高为 $O(\log n)$；取最大最小元素只需要取堆顶元素就好。删除的话需要堆顶和队尾交换，然后自上而下维护，也是 $O(\log n)$ 。

def Insert(heap, x):
	heap.size += 1
	heap[heap.size] = 0
	Increase(heap, heap.size, x)

def Maximum(heap):
	return heap[1]

def ExtractMax(heap):
	swap(heap[1], heap[-1])
	heap.size -= 1
	Heapify(heap, 1)
	return heap[-1]

def Increase(heap, i, x):
	heap[i] += x
	while i > 1 and heap[i // 2] < heap[i]:
		swap(heap[i//2], heap[i])
		i = i // 2

课后题

非递归的 MaxHeapify 用 while True 即可，每次 i = largest，如果发现没有交换，那么退出循环。

def MaxHeapify(heap, i):
	while True:
		l = i.left
		r = i.right
		if l <= size and heap[l] > heap[i]: largest = l
		elif r <= size and heap[r] > heap[i]: largest = r
		else: largest = i
		
		if largest == i:
			return
		swap(arr[i], arr[largest])
		i = largest

6.3-3 偏数学不看了

最坏情况下，从 $\lfloor \frac{n}{2} \rfloor$ 到 1 的每个非叶子结点进行 Heapify 都需要进行到根节点，也就是 $\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor}{h(k)}=\Omega(n\lg n)$ ，这里 $h(k)$ 是节点 k 的高度。

假设是最小堆

def HeapDelete(heap, i):
	heap[i] = INF
	MinHeapify(heap, i)
	heap.size -= 1

第七章 快速排序

代码

def QuickSort(arr, l, r):
	if l < r:
		mid = Partition(arr, l, r)
		QuickSort(arr, l, mid-1)
		QuickSort(arr, mid+1, r)
def Partition(arr, l, r):
	pivot = arr[r]
	left = l - 1
	for i in range(l, r+1):
		if arr[i] <= pivot:
			left += 1
			swap(arr[left], arr[i])
	swap(arr[left+1], arr[r])
	return left + 1

性能

快排的最坏情况发生在，pivot划分两个区域，一边元素为0，一边为 n-1。这时候快排的递推式为：$T(n)=T(n-1)+T(0)+O(n)$ 最终得到 $O(n^2)$。最好情况就是 pivot 均分，这时候 $T(n)=2T(n/2)+O(n)$ 得到 $O(n\log n)$。

快速排序的平均情况更接近 最好情况，因为任何一种常数比例的划分都会生成高度为 $\Theta(\lg n)$ 的递归树，每一层的时间代价都是 $\Theta(n)$，所以运行时间是 $\Theta(n\lg n)$。

随机性

普通 quicksort 的性能强烈依赖 pivot 的选择：如果 pivot 每次都选到最小 / 最大 ，会导致划分极不平衡， 递归深度 n，最终时间复杂度为 $O(n^2)$。随机快排就是 pivot 随机选择一个元素，而不是固定头尾或者中间。

课后题

所有元素都相同时，返回的 q 是选择的 pivot 的下标，所以只有选择中间的元素当 pivot 就行了。

由于无法实现，所以加了常数：

第八章 线性时间排序

基于比较的排序算法下界

最坏情况下，任何比较排序都需要进行 $\Omega(n\lg n)$ 次比较。

没看懂，记住结论

计数排序

def CountingSort(arr, n):
	b, c = [0] * (n+1), [0] * (n+1)
	for i in range(n):
		b[arr[i]] += 1
	for i in range(1, n+1): # 因为是 0-n 一共 n+1 个元素
		b[i] += b[i-1]
	for i in arr[::-1]:
		c[b[i]] = i
		b[i] -= 1
	return c

这个是简易版本，还需要用 max 和 min 计算偏移，这样可以减少空间浪费。

计数排序最简单的思路就是，假如有数组 0,1,2,4,2，那么记录元素 0-4 分别出现 1,1,2,0,1 次，只需要按 0-4 的顺序，输出对应次数的元素即可。但是存在一个问题，就是这个排序是不稳定的。现在需要记录累计次数，1,2,4,4,5 ，然后按照逆向遍历原数组即可。例如，首先遍历到元素 2，找到它的前缀数组值为 4，所以 4 的位置放 2，前缀值减一。那么下一次再遍历到 2 的时候，它就会根据前缀值 3 放在 3 的位置。

时间复杂度是 $O(n+k)$，n 是元素个数，k 是区间范围。

缺点：

• 只适用于整数（或可映射到整数）。
• 范围 k 太大时空间浪费严重。
• 不适合稀疏数据。

基数排序

假设有 n 个元素，每个元素为 d 位

def RadixSort(arr, d):
	for i in range(d):
		SortOnDigit(arr, i)

对于每一次循环，假如对第 i 位采用 $O(n+k)$ 的稳定排序（每个元素有 k 种取值），例如计数排序，那么总耗时 $\Theta(d(n+k))$。

记住从低位到高位排序

桶排序

每个桶内再用其他的排序算法进行排序（比如快排），这样子时间复杂度不还是 $O(n\log n)$ 吗？ 如果要排序的数据有 n 个，我们把它们分在 m 个桶中，这样每个桶里的数据就是 $k=\frac{n}{m}$。每个桶内排序的时间复杂度就为 $O(k\log k)$。m 个桶就是 $m * O((n / m)*log(n / m))=O(nlog(n / m))$。当桶的个数 m 接近数据个数 n 时，$log(n/m)$就是一个较小的常数，所以时间复杂度接近O(n)。

课后题

前缀和，得到累积数组之后，用 c[b] - c[a] 就可以了。

当桶排序所有元素都被集中在一个桶的时候，桶排序就会退化为快速排序，如果出现快排的最坏情况：每次选择的 pivot 都是最大最小值，就会出现 $O(n^2)$ 的时间复杂度。可以通过归并排序或者桶排序，使得最坏情况下也是 $O(n\lg n)$。

第九章 中位数和顺序统计

最值

• 单独获得最大值或者最小值，最少需要 n-1 次比较
• 同时获得最大和最小值不需要 2(n-1) 次比较，只需 $3*\lfloor\frac{n}{2}\rfloor$ ，方法就是同时取两个输入，然后将他们先进行一次毕竟，然后拿较小的元素和最小值比较，较大的元素和最大值进行比较，只需要三次比较。

期望时间为线性的选择算法

选择算法：给定无序数组 A 和整数 k（1 ≤ k ≤ n），找出数组中第 k 小的元素（即排序后位于位置 k 的元素）。

思想类似快排，

• 随机选择一个主元 pivot，对数组进行分区（partition）：左边 < pivot，右边 > pivot，pivot 自己放中间。
• 分区后，pivot 落在最终位置 rank（假设 rank 是 pivot 的排名，从1开始）。
• 如果 rank == k，直接返回 pivot。
• 如果 k < rank，递归在左子数组找第 k 小。
• 如果 k > rank，递归在右子数组找第 (k - rank) 小。

def SelectK(arr, l, r, k):
	if l == r: return arr[l]
	
	pivot_idx = random.randint(l, r)
	swap(arr[pivot_idx], arr[r])
	
	i = l - 1
	for j in range(l, r+1):
		if arr[j] <= arr[r]:
			i += 1
			swap(arr[i], arr[j])
		swap(arr[i], arr[r])
	i += 1
	rank = i - l + 1
	
	if rank == k:
		return arr[]
	elif rank > k:
		return SelectK(arr, l, rank-1, k)
	else:
		return SelectK(arr, rank+1, r, k - rank)

最坏时间为线性的选择算法及其时间分析

Bfprt 算法的思路是选择一个合适的 pivot 使得最坏情况下，时间复杂度还是线性的。选择合适 pivot 的方法是，将数据分为多个区间，递归调用 Bfprt 找到每个区间中位数的中位数。

def bfprt(arr, low, high, k):
    n = high - low + 1
    if n <= 5:
        # 排序子数组并返回第 k 小
        sub = sorted(arr[low:high+1])
        return sub[k-1]
    
    # 步骤2-3: 分组找每组中位数
    medians = []
    for i in range(low, high+1, 5):
        group = arr[i:min(i+5, high+1)]
        group.sort()
        medians.append(group[len(group)//2])
    
    # 步骤4: 递归找中位数的中位数 mom
    mom = bfprt(medians, 0, len(medians)-1, len(medians)//2 + 1)
    
    # 步骤5: 用 mom 分区（类似快速排序 partition）
    # ...（交换 mom 到末尾，partition，返回 rank）
    
    # 步骤6: 递归判断
    if k == rank:
        return mom
    elif k < rank:
        return bfprt(arr, low, pivot_pos-1, k)
    else:
        return bfprt(arr, pivot_pos+1, high, k - rank)

课后题

采用锦标赛制，对元素进行两两比较，最终经过 $\lceil \log_2 n \rceil$ 轮 n-1 次比较得到最小元素。这时候至少有 $\lceil \log_2 n \rceil$ 个元素直接输给过最小元素，第二小元素只有可能在这里面。这时候比较 $\lceil \log_2 n \rceil - 1$ 次就能得到里面最小元素，也就是第二小元素。

k分位数是大小为n的集合（比如数组）里面的k-1个数，它们把有序的集合分为k个分组，任何两个个分组之间的大小之差的绝对值不超过1（有点类似于平衡二叉树），比如集合{3， 5， 9， 4， 2， 1， 6， 8， 9， 10， 12， 7， 6}，排序后为{1， 2， 3， 4， 5， 6， 6， 7， 8， 9， 9， 10， 12}，它的4（k = 4）分位数为{4， 6， 9}， 分组后的子集合分别为{1， 2， 3， 4}， {5， 6， 6}， {7， 8， 9}， {9， 10， 12}。要求从集合中找出这k-1个数，并且时间复杂度为O(nlgk)。

思路：如果对这 k-1 个数分别使用 Order Statistics 算法，第一次找出第4小的数，第二次找出第7小的数，第三次找出第10小的数，虽然每次的时间复杂度为 O(n)，但 k-1 次则为$O(nk)$，不是 $O(nlgk)$。所以可以采用分治的思路。

1. 假如需要找到 k 分位数，k=4
2. 那么就先减半找到 k=2 分位数，这时候时间复杂度 $O(n)$
3. 然后我们递归的处理左边部分和右边的分位数

第十三章 红黑树

二叉搜索树没有控制树高，红黑树在二叉搜索树基础上，通过在节点数增加颜色，控制没有一条路径会比其他路径长出 2 倍，使得近乎平衡。

• 根叶黑

• 不红红

• 黑路同

• 有 n 个节点的红黑树，高度至多为 $2lg(n+1)$

• 一棵黑高为 K 的红黑树中，结点最多为 $2^{2k+1}-1$（红黑交替），最少 $2^{k+1}-1$ （全黑）

不考画图，随便看看

第十四章 数据结构的扩张

顺序查找树

前面学的 Order-Statistics 算法可以在 $O(n)$ 的时间内找到第 i 个元素，但是如果需要进行多次查找操作，时间复杂度还是蛮高的。顺序查找树能做到一次预处理之后，每次查找的时间复杂度为 $O(\lg n)$。

它在红黑树基础上，每个节点维护了一个 size 属性，标志了以自己为根的子树个数，它的功能包括：

• 根据元素 x 获得它的 rank
• 根据 rank 获取 x

def Rank2Ele(t, r):
	rank = t.left.size + 1
	if rank == r: return
	elif rank > r: return Rank2Ele(t.left, r)
	else: return Rank2Ele(t.right, r - rank)
	
def Ele2Rank(t, x):
	if t == x: return t.left.size + 1
	elif t > x: return Ele2Rank(t.left, x)
	else: return t.left.size + 1 + Ele2Rank(t.right, x)

简单来说：如果扩张属性只影响到父节点或只影响到子节点，就可以在红黑树上扩张。

能不能拓展深度属性呢？ 不行，假如根节点删除了，那么下面所有子节点都需要修改深度–，影响的是 $O(n)$。

区间树

• 区间树以红黑树为基础
• 区间树的节点关键词存储的是一个区间 i.left, i.right
• 区间树节点附加信息是 max，代表节点所在的所有子树，最大的右端点

由于 x.max = max(x.left.max, x.int.right, x.right.max) ，根据定理可以在红黑树上扩展。

def IntervalSearch(T, i):
	res = []
	x = T.root
	if x != T.nil and overlap(x.i, i):
		res.append(x)
	if x.left != T.nil and x.left.max > i.left:
		IntervalSearch(x.left, i)
	elif x.right != T.nil:
		IntervalSearch(x.right, i)

课后题

def i_after_x(T, x, i):
	idx = Ele2Rank(T, x)
	return Rank2Ele(T, i + idx)

根据元素查 rank 和你操作的时间复杂度都是 $O(\lg n)$，所以还是 $O(\lg n)$。

可以，因为当一个节点的颜色反转时候，它只会影响父节点的黑高，例如红变黑，那么父节点黑高++，只会在这颗子树向上或者向下影响，最多 $O(\lg n)$。

def min_overlap(T, i):
	res = T.nil
	rec = INF
	x = T.root
	while x != T.nil:
		if overlaps(x.int, i) and x.int.left < rec:
			rec = x.int.left
			res = x
		if x.left != T.nil and x.left.max >= i.right:
			x = x.left
		else:
			x = x.right
	return res

第十五章 动态规划

思想&步骤

• 解决的是寻找问题的一个最优解
• 具备的两个要素：最优子结构和子问题重叠
  • 问题的最优解由相关子问题的最优解组合而成
  • 子问题重叠：例如斐波那契数列，重复求同一个子问题
• 步骤：
  • 识别最优解的特征
  • 递归的定义最优解的值（就是状态转移方程）
  • 自底向上求解

和分治法区别

• 分治法是分解为互不相干的子问题求解之后合并
• 动态规划是重叠的子问题

算法设计

例：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。你可以认为每种硬币的数量是无限的。

假设我们用 Func(coins, amount) 求解所需的最少的硬币个数，并且 硬币为 1 和 2，那么可以把他分解为，求解 amount-1 所需最少硬币和 amount -2 所需最少硬币的最小值 + 1。写成递推式即为：$T(n)=min(T(n-1)+T(n-2))+1$

def MinimumCoins(coins, amount):
	dp = [INF] * (amount+1)
	dp[0] = 0
	for i in range(1, len(dp)):
		for coin in coins:
			if i - coin < 0: continue
			dp[i] = min(dp[i], dp[i-coin]) + 1
	return dp[amount]

这个题思路和凑硬币完全一样，把最小值变成最大值，就行了。

m[i][j] 依赖于区间更短的子问题，所以必须按区间长度递增计算，常见顺序是：

for l = 2 to n // 链长度  
 for i = 1 to n−l+1  
  j = i + l − 1  
  计算 m[i][j]

这是一个典型的区间 DP。

def MatrixMultiply(m):
	dp = [[INF for i in range(n+1)] * (n+1)]
	for i in range(n+1):
		dp[i][i] = 0
	for l in range(2, n+1):
		for i in range(1, n+1-l):
			j = i + l - 1
			for k in range(i, j):
				cost = dp[i][k]+dp[k+1][j]+m[i].p*m[k].q*m[j].q
				if cost < dp[i][j]:
					dp[i][j] = cost
					res[i][j] = k

例：给定一个长度为 n 的整数序列 A[1…n]（可正可负），要求找一个连续子段 A[i…j]，使其元素和最大。

ans = -INF
dp = [0]*(n+1)
dp[1] = A[1]
for i in range(2, n+1):
	dp[i] = A[i] if dp[i-1] < 0 else A[i] + dp[i-1]
	ans = max(ans, dp[i])
return ans

注意子序列和子串区别

for i in range(1, m+1):
	for j in range(1, n+1):
		if x[i] == y[j]:
			dp[i][j] = dp[i-1][j-1] + 1
		else:
			dp[i][j] = max(dp[i-1][j], dp[i][j-1])

找出两个长度分别为m和n字符串序列的最长公共字串（字串为下标连续的子 序列），试： 
（1） 先给出朴素算法的算法思想、伪代码及计算时间复杂度 
（2） 再给出算法改进思路或一个更有效的算法

这个问题可以结合 最长公共子序列 和 最长连续子串 两个问题。令 dp[i][j] 为 以 X[i] 和 Y[j] 结尾的最长公共子串长度，若字符相等：dp[i][j] = dp[i−1][j−1] + 1 ，若字符不等：dp[i][j] = 0。

LongestCommonSubstring(X, Y):
    n = length(X)
    m = length(Y)
    create array dp[0..n][0..m]
    maxLen = 0
    endPos = 0

    for i = 0 to n:
        dp[i][0] = 0
    for j = 0 to m:
        dp[0][j] = 0

    for i = 1 to n:
        for j = 1 to m:
            if X[i] == Y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > maxLen:
                    maxLen = dp[i][j]
                    endPos = i
            else:
                dp[i][j] = 0

    return maxLen   // 子串为 X[endPos-maxLen+1 .. endPos]

例：给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

import math
class Solution:
    def numSquares(self, n: int) -> int:
        pow = [i**2 for i in range(1, math.floor(math.sqrt(n))+1)]
        dp = [float("inf") for _ in range(n+1)]
        dp[0] = 0
        for i in range(1, n+1):
            for k in pow:
                if i-k >= 0:
                    dp[i] = min(dp[i], dp[i-k] + 1)
        return dp[n]

课后题

因为归并排序这种分治算法不会出现重叠子问题，所以不需要备忘技术记录重复结果。

1 0 0 1 1 0

• 对于 $2 \times \min(m,n)$ 空间复杂度的算法，由于每次遍历只需要用到 dp 数组的当前行和上一行，所以可以只需要保留这两行
• 对于 $\min(m,n)$ 空间复杂度的算法，我们可以仅仅保留一行 dp 数组，执行到 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 时候，由于 dp[i][j-1] 还没被 dp[i][j] 覆盖可以直接读取；dp[i][j] = dp[i-1][j-1] + 1 里面的 dp[i-1][j-1] 已经被 dp[i-1][j] 覆盖，所以需要单独的变量记录就可以了。

第十六章 贪心算法

思想&对比

• 核心思想：在构造解的过程中，每一步都做出当前看来最优（局部最优）的选择，并期望通过一系列局部最优选择最终得到全局最优解。
• 和动态规划的区别：dp 只要求有最优子结构，贪心还要求满足贪心选择性质：存在一个最优解，其第一步选择等于贪心算法所做的选择。

哈夫曼树

贪心正确性证明：假设树叶节点频率最小的两个节点 a，b 的频率分别是 fa 和 fb，全部元素中，频率最小的结点为 x 和 y，频率为 fx 和 fy。那么用 xy 替换 ab，他们仍然在最深处，并且加权路径长度只可能小等于 原先的 ab，所以得到了另一课最优的编码树。

算法设计

例：给定 n 个活动， 活动 i 的开始时间为 $s_i$，结束时间为 $f_i$，选择尽可能多的互不冲突的活动。

1. 按活动结束时间递增排序；
2. 选择第一个结束最早的活动；
3. 在剩余活动中，选择开始时间 ≥ 当前活动结束时间的、结束最早的活动；
4. 重复直到无法选择。

贪心性质证明：

设 A* 是任意一个最优解（即包含最多活动的集合），其中第一个活动是 b，其结束时间为 f_b。由于 a 是所有活动中结束时间最早的活动，因此有：f_a ≤ f_b。

分两种情况讨论：

1. 如果 a = b：那么 A* 本身已经包含贪心选择 a，命题成立。
2. 如果 a ≠ b：那么可以用 a 替换 b，因为 a 比 b 早结束，不会影响后面活动。并且替换后活动数量一致，仍然是最优解。

例：有 n 个物品，物品 i 的价值为 $v_i$，重量为 $w_i$，背包容量为 W，每个物品可以取任意比例（可分割）。

1. 按照单位价值从高到低排序
2. 依次选择物品加入背包
3. 如果最后一件物品无法全部装入，则计算可以装入的比例，然后按比例装入。

贪心性质证明：设 a 为单位重量价值最大的物品。若某最优解不包含 a，则从中取出重量为 x 的低单位价值物品，用同重量的 a 替换，总价值不减。反复交换可得包含 a 的最优解，故贪心选择性质成立，小数背包贪心算法正确。

课后题

• 算法思路：按照重量排序，每次选重量最小的
• 贪心性质证明：
  • 设 $S^$ 是任意一个最优解，$S^$ 选择的第一个元素下标是 i
  • 假设按照贪心算法选择的第一个元素下标为 0
  • 假如 i==0，那么最优解第一个元素就是贪心
  • 假如 i != 0，那么最优解的第一个元素肯定比 0 重价值低，那么替换为 0 就可以得到更优解。

• 算法思路：对点集进行排序，每次都取剩余点集中最靠左的点当新区间的左端点
• 贪心性质证明：
  • 假设：$x_1$​ 是当前最左的点，贪心算法选择的第一个区间为 $I_a = [x_1,; x_1+1]$
  • 设 $S^*$ 是任意一个最优解，覆盖 $x_1$ 的区间为 $I_b = [l_b,; l_b+1]$，那么必有 $l_b \le x_1 \le l_b + 1$。
  • 按照思路，贪心区间的右端点为 $r_a = x_1 + 1$，有 $r_b \le r_a$。
  • 假设 $I_a = I_b$ 则最优解 $S^*$ 本身已经包含贪心选择的区间，命题成立。
  • 假设 $I_a \ne I_b$，则新区间 $S’ = (S^* \setminus {I_b}) \cup {I_a}$，这是一个更优解。

• 斐波那契数列构造的哈夫曼树，所有节点左子树都只有一个节点。
• 最优前缀码为：0,01,001,0001

实验二 回溯法

解空间树

根据问题的不同，解空间通常表现为以下三种形式之一：

1. 子集空间（子集树）
   • 每个元素只有“选”或“不选”两种状态。
   • 常见于 0-1 背包、子集和问题。
   • 解空间树通常是一棵二叉树。
2. 排列空间（排列树）
   • 元素的顺序不同即构成不同解。
   • 常见于全排列、TSP 等问题。
   • 树的分支数随层数递减。
3. 组合空间
   • 介于子集和排列之间。
   • 常见于从 n 个元素中选 k 个的组合问题。

算法设计

n 后问题

问题描述： 在 n×n 的棋盘上放置 n 个皇后，使得任意两个皇后不在同一行、同一列或同一对角线上。

def n_queen(chess, line):
	if line == n+1 and check(chess):
		print(chess)
	for i in range(n):
		chess[line][i] = True
		# 可以在这里剪枝，用col记录那些列有皇后了
		# if i in col:
		#     continue
		# else:
		#     col[i] = True
		
		n_queen(chess, line+1)
		chess[line][i] = False
		# col[i] = False

0-1背包

问题描述： 每个物品只能选或不选，在容量限制下最大化总价值。

void dfs(int i, int cw, int cv) {
    if (i == n) {
        ans = max(ans, cv);
        return;
    }

    // 不选第 i 个
    dfs(i + 1, cw, cv);

    // 选第 i 个
    if (cw + w[i] <= W) {
        dfs(i + 1, cw + w[i], cv + v[i]);
    }
}

TSP 问题

问题描述： 给定 n 个城市及其距离，寻找一条经过每个城市一次并回到起点的最短回路。

visited = [0]*(n+1)
def dfs(dis):
	if sum(visited) == n:
		ans = min(ans, dis)
		return
	for i in range(1, n+1):
		if visited[i]: continue
		visited[i] = True
		dfs(dis+cost[i])
		visited[i] = False

第十七章 平摊分析

聚合分析

对于一个栈，假设有 pop, push, multi-pop(n) 三个操作，时间复杂度分别为 O(1), O(1) 和 O(n)。进行 n 次操作，每次操作任选一个，那么时间复杂度是多少？如果按最坏情况，每次操作都是 multi-pop，那么总时间复杂度为 $O(n^2)$ 。但实际情况是，push 一次才能 pop一次，所以 pop 和 multi-pop 的次数和 push 次数相关。经过一系列证明可以得到实际的时间复杂度是 O(n)，所以平均到每个操作，他们的摊还代价是 O(1)。

同样对于一个 n 位二进制串 0000000，每次进行 Increment 操作，第一次只需要改变一个值，第二次需要改变两个 01 -> 10，第四次需要根本三个 011 -> 100，最终需要改变 n 个值。所以进行 n 次操作，最坏情况是 $O(n^2)$。但实际上每 $2^i$ 次操作翻转位数才会加一，所以经过一系列证明，最坏情况的时间是 O(n)，他们的摊还代价是 O(1)。

核算法

假设我们实现一个动态数组，支持push_back，每次容量不够时翻倍扩容。

• 大多数插入代价1（只放一个元素）。
• 偶尔扩容时代价≈当前size（要复制）。

用核算法：

• 每个插入操作我们收取摊还费用 â = 2（单位代价）。
• 使用规则：
  • 1单位支付当前插入本身（放新元素）。
  • 1单位存入银行（为这个新元素“预存”未来的复制费用）。

当发生扩容（从k到2k）时：

• 需要复制k个旧元素，每个旧元素在之前插入时已经为它预存了1单位。
• 总共可以从银行取出 k 单位。
• 实际扩容复制代价 ≈ k

容易归纳证明：银行余额始终 ≥ 0（实际上总是正的）。

因此：

• 每个插入的摊还代价 = 2 = O(1)
• n次插入的总摊还费用 = 2n = O(n)
• 总实际代价 ≤ 2n = O(n)（严格上界）

势能法

首先，我们定义状态 S 为当前某一数据结构的状态。该状态反应出该数据结构的元素值、元素个数等信息。然后，我们定义一个势能函数 $\Phi(S)$，表示当该数据结构处于状态 S 下的势能。和物理中的定义类似，你需要保证你定义的这个势能涵函数在初始时值为 0，且在算法执行的任意过程中值非负。并且势能的变化量在一定程度上可以反应出该对象的形态改变程度。

对于每个操作，我们定义摊还代价 $c’=c+\Phi(S’)一\Phi(S)$。其中，c 表示该操作的实际成本，S和S’表示该操作前后数据结构的状态。直观地，均摊成本等于实际成本加上势能变化量。

对于动态数组扩容的例子，我们定义势能函数为 $\Phi(S)=2n-m$，n 是动态数组实际长度，m 是总长度。这么定义是因为能保证大于 0 ，并且插入元素会导致 n 和 m 改变然后势能变化。

摊还代价都是 3 也就是 O(1) 的时间。

课后题

感觉不会考，全是数学证明

第十九章 二项堆

为什么需要二项堆

优先队列通常是使用二叉堆这个数据结构来实现，在某些应用中，合并两个优先队列是核心需求，而二叉堆的 Union 操作需要把另一个二叉堆的元素逐个插入，所以时间复杂度是 $O(n\lg n)$。二叉堆的目的就是维持优先队列的性质，并且降低合并操作的时间复杂度。

定义和存储结构

先说二项树：

• 假设树高为 k，有 $2^k$ 个节点
• 第 i 层有 $C_k^i$ 个节点
• 根的度最大且为 $C_k^1=k$
• 二项树 $B_k$ 是有两颗 $B_{k-1}$ 合并而成，将一棵 $B_{k-1}$ 的根作为另一棵 $B_{k-1}$ 根的最左孩子。

二项堆是满足下述条件的二项树的集合：

• H 中的每棵二项树满足最小堆性质（根小于任意子节点）
• 对任意的非负整数 k，H 中至多有一棵二项树根的度为 k

二项堆中的所有二项树的根节点由一个单链表连接，按照度（或者说二项树高度）增序。二项树的节点定义如下：

@dataclass
class Node:
	p: Node # 父节点
	key: int # 关键字
	degree: int # 度：子节点个数，就是C_k^i
	child: Node # 左孩子
	sibling: Node # 右兄弟

先说一下 Minimum 操作，前面说过“二项堆中的所有二项树的根节点由一个单链表连接”，所以需要用一个线性查找，遍历所有根节点。假设二项堆总节点数为 n，最多 ⌊log₂ n⌋ + 1 棵树，所以时间复杂度为 $O(\lg n)$。

二项堆每棵树都是某个 Bₖ，任意两棵树的 degree 不同，所以 1+2+4+8+…=n。

合并操作

• 把两个二项堆链表合成一个链表，仍然按照度排序根节点，复杂度是 $O(\lg n)$（因为根节点最多 ⌊log₂ n⌋ + 1 个）
• 对所有度相同的二项树进行合并，假设待合并的两棵树为 $B_{k-1}$
  • 将关键字较大的根挂到关键字较小的根下（第一个左孩子），得到一个 $B_k$ 的新二项树
  • degree+1，树高也+1
• 每次二项树合并时间复杂度为 O(1)，最坏情况每棵树度都相同，合并 $O(\lg n)$ 次，时间复杂度 $O(\lg n)$。

第二十一章 不相交集数据结构

概念

不相交集用于维护一组动态变化的集合划分，要求这些集合两两不相交。其核心目标不是存储集合中的元素内容，而是高效维护“元素属于哪个集合”以及“集合是否需要合并”。

形式化定义如下：给定一个全集 $S = {x₁, x₂, …, xₙ}$，不相交集维护的是 S 的一个划分 ${S₁, S₂, …, Sₖ}$，满足：

• Sᵢ ≠ ∅
• Sᵢ ∩ Sⱼ = ∅（i ≠ j）
• ⋃ Sᵢ = S

支持三种基本操作：

1. MAKE-SET(x)：创建一个新集合，仅包含元素 x。
2. FIND-SET(x)：返回包含 x 的集合的一个代表（representative）。
3. UNION(x, y)：将包含 x 和 y 的两个集合合并为一个集合。

注意 find-set 返回的不是集合，而是集合的代表 FIND-SET(x) == FIND-SET(y) 可以判断两个元素是不是在同一个集合

实现方法

链表

每个集合用一个链表表示：

• 链表中存储该集合的所有元素：head → a → b → c

• 每个节点存一个指向“集合头节点”的指针：a.head = b.head = c.head = head

• 头节点代表该集合（作为 representative）

• make-set(x)：创建一个只含 x 的链表，O(1)

• find-set(x)：返回 x.head，O(1)

• union(x, y)：把 y 去掉 head 连到 x 尾部，O(n)

FIND 非常快，但合并代价高

森林(就是并查集)

• make-set(x)：parent[x] = x，O(1)
• find-set(x)：while x = parent[x]: return x，O(logn)，树高
• union(x, y)：root_x = find_set(x), root_y = find_set(y), parent[root_y]=root_x，O(logn)，时间复杂度取决于 find-set，不控制会退化为链表

采用路径压缩在find_set时候把路径上所有节点直接指向根，可以让 find-set 和 union 是常数时间。

应用

1. kruskal：用并查集判断 u 和 v是否连通，不连通则选择该边
2. 无向图连通分量：对每条边的两个节点 u 和 v 进行 union，最后几个根节点就是几个连通分量

课后题

先找到根，然后自底向上更新全部 parent 为根。

def find_set(T, x):
	root = x
	while T[root] != root:
		root = T[root]
	while x != root:
		p = T[x]	
		T[x] = root
		x = p
	return root

第二十二章 图论算法

DFS 和 BFS

• 白色节点是未访问过的节点
• 灰色节点是已访问，但是还没有搜索周围节点的节点
• 黑色节点表示该结点的所有邻接结点均已被检查完毕

颜色机制的本质作用是保证 每个结点最多被发现一次，用 visited 数组一样效果

最小生成树

安全边：假设 A 是最小生成树的一个子集，假如把一条边加入 A 后它仍然是最小生成树的子集，那么它就是安全边。

最小生成树的算法就是不断找到一条安全边，把它加入集合中。最终集合包含所有边，那么他就是最小生成树。

• Prim：
  • 加点法：然后 S 是已选择点的集和，那么不断挑选离 S 最近的点加入，连上那条边
  • 数组表示的话O(V^2)，用最小优先队列(二叉堆)是O(ElogV)。二叉堆 Extract-minimum 时间复杂度是 logV，总开销 VlogV。但是每次加点之后，需要更新其他点离 S 的最近距离，也就是二叉堆的 decrease-key 操作，时间复杂度是 O(logV)，最坏情况是 E 次，所以 O(ElogV)。
• Kruskal：
  • 加边法：不断选择权值最小并且不形成连通分量的边
  • 时间复杂度O(ElogV)，首先给边排序的时间复杂度是 $O(E\lg E)=O(E\lg V)$，然后一共 E 次循环，每次循环最多需要 2 次 find 1次 union，如果经过路径压缩，那么摊还代价是 $\alpha(V)$ ，所以总时间复杂度 $O(E*\alpha(V))=O(E)$，排序占主导所以是 O(ElgV)

单源最短路

δ(s, v) 与 d[v] 是什么？

• δ(s, v)：从源点 s 到 v 的真实最短路径长度（理论值）；
• d[v]：算法运行过程中维护的上界估计，始终满足 d[v] ≥ δ(s, v)。

边松弛：

若 d[v] > d[u] + w(u, v)：

• d[v] = d[u] + w(u, v)
• π[v] = u

Bellman-Ford 算法：

1. 设置 dis[起点]=0，dis[其他点]=inf
2. 进行 v-1 轮遍历
   1. 遍历每一条边 <u,v >，对 dis[v] 进行更新，看看能不能 dis[v] = dis[u]+w[u,v] 松弛
3. 最后遍历一轮，如果还有更新，说明不能收敛，有负权环，return False。
4. 时间复杂度 O(EV)
5. 可以用于负权图，不能负权回路

Dijkstra 算法：

1. 设置 dis[起点]=0，其他为inf
2. 更新起点相连节点的dis
3. 按照dis，遍历未访问的所有节点
   1. 将节点设为 visited
   2. 更新这个节点相连节点的dis
4. 和 prim 算法一样，时间开销受限于二叉堆的 decrease-key 操作，时间复杂度是 O(logV)，最坏情况是 E 次，所以 O(ElogV)。
5. 如果用斐波那契堆进行优化（二叉堆优化），那么开销是 O(VlogV+E)。
6. 用于非负权、有向图，可以有环

DAG 算法

1. 只能有向无环图 -> 这样才保证存在拓扑排序，拓扑排序保证在处理 u 之前，所有可能到达 u 的前驱顶点 x 的最短路径都已经被正确计算
2. 先进行一次拓扑排序
3. 按拓扑排序扫描顶点，对每个顶点 u：
   • 对每条出边 (u, v) 进行松弛
4. 时间复杂度 O(E+V)，受限于拓扑排序开销

多源最短路

floyd 的思路就是依次增加中转顶点，看 i 和 j 之间的距离能不能通过中转顶点缩减。

def floyd():
	for k in range(V):
		for i in range(V):
			for j in range(V):
				new_dis = dis[i][k] + dis[k][j]
				if (new_dis < dis[i][j]):
					dis[i][j] = new_dis
					path[i][j] = path[k][j]

path[i][j] 表示：“在从 i 到 j 的最短路径上，j 的前一个顶点是谁” 如果 d[i][j] > d[i][k] + d[k][j] ，说明 i → … → k → … → j。所以 j 之前一个顶点应该是 d[k][j] 找 i - j 路径的方法就是，不断递归找 d[i][j]=k 然后找 d[i][k]

时间开销 $O(V^3)$，适合稠密图。

Johnson 算法

• 那么对每个节点进行 Dijsktra，用斐波那契堆开销是 O(VlogV+E)，总时间O(V^2logV+VE)。如果用二叉堆是O(VElogv)
• 但是 Dijsktra 只能用于非负权图，所以需要用 bellman-ford 计算一个势能函数，得到新的权值，代替原先可能为负数的权值
  • 假如一个新节点s，对其他所有节点的dis=0
  • 然后 bellman-ford 得到 s 对其他节点 v 的距离，作为 h(v)
  • 然后每条边 <u,v> 新的权重就是 w[u,v] +h(u)-h(v)
• 适用于稀疏图

第三十一章 数论算法

最大公约数

欧几里得算法

代码

def gcd(a, b):
	if b == 0: return a
	else: return gcd(b, a % b)

时间复杂度为：O(log(min(a, b))) 或 O(log(max(a, b)))

证明

我们首先假设有两个数 $a$ 和 $b$，其中 $a$ 是不小于 $b$ 的数，记 $a$ 被 $b$ 除的余数为 $r$，那么 $a$ 可以写成这样的形式：

其中 $q$ 是整数。现在假设 $a$ 和 $b$ 的一个约数为 $u$，那么 $a$ 和 $b$ 都能被 $u$ 整除，即

$s$ 和 $t$ 都是整数。这样可以得出：

所以 $r$ 也能被 $u$ 整除，我们能得到一般规律如下：

$a$ 和 $b$ 的约数也整除它们的余数 $r$，所以 $a$ 和 $b$ 的任一约数同时也是 $b$ 和 $r$ 的约数。

反过来可以得出：

$b$ 和 $r$ 的任一约数同时也是 $a$ 和 $b$ 的约数。

因此，我们可以推出：$a$ 和 $b$ 的约数的集合，全等于 $b$ 和 $r$ 的约数的集合，所以 $a$ 和 $b$ 的最大公约数，就是 $b$ 和 $r$ 的最大公约数。

根据递推性质，我们可以不断减小 $b$ 使得公式变为 $gcd(x,0)$，结果就是 x。

扩展欧几里得算法

代码

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a / b) * y1
    return gcd, x, y

证明

欧几里得算法产生如下除法序列：

1. $a = q₁ b + r₁ (0 ≤ r₁ < b)$
2. $b = q₂ r₁ + r₂ (0 ≤ r₂ < r₁)$
3. $r₁ = q₃ r₂ + r₃ (0 ≤ r₃ < r₂)$
4. …
5. $r_{k-2} = q_k r_{k-1} + r_k$
6. $r_{k-1} = q_{k+1} r_k + 0$

则 $gcd(a, b) = r_k$ 最后一个非零余数。现在从后往前回代，证明 $r_k$ 可以表示为 $a$ 和 $b$ 的线性组合。

1. 从倒数第二步： $r_k = r_{k-2} - q_k r_{k-1}$ （这是 $r_{k-2}$ 和 $r_{k-1}$ 的线性组合）
2. 将 $r_{k-1}$ 代入上一式： $r_{k-1} = r_{k-3} - q_{k-1} r_{k-2}$ → $r_k = r_{k-2} - q_k (r_{k-3} - q_{k-1} r_{k-2}) = (1 + q_k q_{k-1}) r_{k-2} - q_k r_{k-3}$
3. 继续回代，最终所有余数都会被表达为更早的余数，直至：
   • $r₁$ 用 $a$ 和 $b$ 表示：$r₁ = a - q₁ b$
   • $b$ 用 $b$ 表示（自身）

最终，$r_k$（即 gcd）将被表达为 $a$ 和 $b$ 的整数系数线性组合： gcd(a, b) = r_k = a x + b y

线性模方程

问题背景

在模 n 的世界里，只剩下 n 个“基本元素” ${0, 1, 2, …, n−1}$，每一个元素实际上代表一个无限集合 $[k] = { k + tn | t ∈ ℤ }$。例如在模 7 的世界里：

• 0 代表 ${…, −14, −7, 0, 7, 14, …}$
• 3 代表 ${…, −11, −4, 3, 10, 17, …}$

因此我们可以写出 $7 \equiv 12 (\text{mod} 5)$，因为它们对 5 的余数相同。而线性模方程解决的就是：

其中 a, b, n 是已知整数，n > 0，x 是未知整数，我们要求的就是 x 在模 n 意义下的解。但是在模 n 的世界里，除法并不天然存在。所以线性模方程解决的是：

在模运算体系中，什么时候可以做“除法”，以及怎么做。

除法存在的条件

假设 $d=\text{gcd}(a, n)$，当且仅当 $d | b$（整除） 时，方程 $ax \equiv b (mod , n)$ 有解，并且在模意义下存在 d 个不同的解。

怎么做

def linear_mod(a, b, n):
	d, x, y = gcd_extened(a, b)
	if d % b: return -1
	x0 = (x * b / d) % n
	for i in range(n):
		print(x0 + i * n / d) % n

感觉不考，具体原理看不懂

手算

例： 求 $35x=10(mod 50)$ 的所有解

1. 先判断有没有解：$d=gcd(35, 50)=5$ ，5 整除 10 所以有唯一解，解的数量为 5
2. 等式两边同除 d 得到 $7x \equiv 2(mod 10)$
3. 计算模 50 空间下 7 的逆元，就可以把 x 的系数消掉，经过计算 $7 \times 3 = 1 (mod 10)$
4. 等式两边同乘 3，得到 $x \equiv 6(mod 10)$
5. 所以解为 $x=6 + 10t$

逆元其实就是普通意义上的相反数，我们需要求 $kx=b$ 里面 k 的相反数，这样两边同乘就可以去掉 x 的系数。

中国余数定理

中国余数定理主要解决一组线性同余方程组的求解问题，即： 给定多个模数和对应的余数，求一个整数 x 使得它同时满足所有这些同余条件。简单地说就是线性模方程组求解。

假设 $m_1,m_2,…,m_k$ 两两互质，那么方程组在模 $M=m_1m_2…m_k$ 空间下有唯一解。

解方程组步骤：

1. 计算 $M$ 和 $M_i$
   1. $M=m_1m_2…m_k$
   2. $M_i=M / m_i$
2. 计算 $M_i$ 在模 $m_i$ 下的乘法逆元 $M_i^{-1}$ ，$M_i · M_i^{-1} ≡ 1 (mod , m_i)$
3. 计算 $c_i=M_i \times (M_i^{-1} \mod m_i)$
4. $x = \sum{c_i \times a_i (mod , M)}$
5. 结果为 M*k+ x，k 为任意整数

例：找出被9,8,7除时，余数分别为1,2,3的 x

1. $M=9\times8\times7=504$
2. $M_1=56,M_2=63,M_3=72$
3. 计算逆元
   1. $56\times M_1^{-1}=9N+1 \rightarrow M_1^{-1}=5$
   2. $63\times M_2^{-1}=8N+1 \rightarrow M_2^{-1}=7$
   3. $72\times M_3^{-1}=7N+1 \rightarrow M_3^{-1}=4$
4. 计算 c
   1. $c_1=56 \times (5 \mod 9)=280$
   2. $c_2=63 \times (7 \mod 8)=441$
   3. $c_3=72 \times (4 \mod 7)=288$
5. 求和 $x=1280+2441+3*288=2026 \mod 504 = 10$
6. 结果为 504k+10

RSA算法

1. 随机挑两个大素数 p 和 q
2. $n=pq$ 且 $\phi(n)=(p-1)(q-1)$
3. 找一个 e 使得 $gcd(e, \phi(n)) = 1$ ，也就是找一个和 $\phi(n)$ 互质的数
4. 计算模 $\phi(n)$ 空间下 e 的逆元 d 使得：$ed \equiv 1 (mod , \phi(n))$
5. 公钥 (n, e)，私钥 (n, d)。知道了 e 但是不知道 p 和 q 没法推出逆元

素数算法

简单素数测试

判断 n 是不是素数，只要用 $2,…,\sqrt{n}$ 和它进行除法就知道了。

伪素数测试

根据 Fermat 小定理：若 p 是素数，则对任意整数 a 满足 p 不整除 a，有 $a^{p−1} ≡ 1 (mod , p)$。所以我们就想到它的逆否命题，对任意整数 a，且 p 整除 a，假如 $a^{p−1} \not\equiv 1 (mod , p)$，那么 p 不是素数。如果等式成立，那么则称 p 是一个基为 a 的伪素数。

整除的概念是：如果存在整数 k，使得 $a = b \cdot k$，那么称 b 整除 a。

那么称 bbb 整除 aaa，记作：

def pseudo_prime(n):
	return math.pow(2, n-1) % n == 1

错判合数为素数：Carmichael 数（561、1105、1729……）

MR算法

Fermat 测试的问题在于：存在 Carmichael 数，使所有 a 都通过测试。MR 的改进在于：对任意合数 n，不会对所有 a 都“伪装成功”。若 n 是合数，则至少 3/4 的 a 能在 MR 测试中暴露 n 是合数。因此 MR 给出了一个统一的错误概率上界，而 Fermat 测试没有。

1. 根据整数分解定理，任意整数都可以唯一的分解为 2 的若干次幂 × 一个奇数，所以令 $n-1 = 2^s \times d$
2. 检查 ${a^d, a^{2d}, a^{4d}, …, a^{2^{s−1}d}}$，如果 出现 −1（mod n），就符合素数应有的行为；

但是 仍然会出现错判素数，时间复杂度为 $O(T \times \lg{N})$，T 是检测轮次。

第三十二章 串匹配

朴素

for i in range(n):
	for j in range(m):
		if T[i+j] != P[j]:
			break

• 最坏情况下时间复杂度 $O(nm)$
• 最后情况下时间复杂度 $O(n)$，每次第一个字符就失配

Rabin-Karp

Rabin-Karp 算法先是比较模式串 P 与文本子串 T[s+1 … s+m] 的哈希值，只有当哈希值相等时，才进行一次逐字符验证，这是一种“先粗筛、再精查”的思想。哈希函数为：

• q 是一个大素数用于取模
• d 要求大于字母表大小，如 ASCII 可以取 256

for i in range(n):
	if not hash(T[i;i+m], P): continue
	for j in range(m):
		if T[i+j] != P[j]: break

• 最坏情况时间复杂度 $O(nm)$，每个哈希值都符合
• 最好情况时间复杂度 $O(n+m)$，哈希时间+匹配时间

有限自动机

将模式串 P 构造成一个确定有限自动机（DFA），在扫描文本时： •每读入一个字符，只进行一次状态转移，不回退文本指针。

具体例子：模式串 P = “aab” 字母表 Σ = {a, b}