【数据结构与算法2】算法篇：用3x2审视算法课的算法部分

总而言之是叽里呱啦一些《算法导论》笔记
基础算法案例，分治，比较算法与随机化，动态规划，贪心，最短路径，
网络流，回溯，在线算法，P/NP，近似算法

基于复旦大学2025-2026秋软件工程专业黄橙老师“算法设计与分析”课程内容，感谢老师的辛勤付出！
相关配套书籍为《算法导论》，课程中选取了其中的大部分主干内容，不涉及过难的内容。
本文是学习过程中的两篇笔记中的第二篇（算法篇），加入了个人的理解和一些辅助学习的脚手架。
如有不妥当之处还望多指正，可以在下面评论区或者 https://github.com/Meredith2328/meredith2328.github.io 里提issues反馈。

直觉+过程+伪代码：
上下文、复杂度，
边界、核心设置，
不变量、自然语言解释。

Lec1 数学基础√
Lec2 分治√
Lec3 比较算法与随机化√
Lec4 哈希不太能用这个结构讲√
~~Lec5 布隆过滤器不太能用这个结构讲~~
Lec6 动态规划必须可以√
Lec7 贪心可以√
Lec8 摊还分析主要是数学分析方法，略过√
Lec9 最短路径可以√
Lec10 网络流可以√
Lec11 回溯可以√
Lec12 在线算法可以√
Lec13 线性规划主要是数学分析方法，略过√
~~Lec14 密码算法只是导论，略过~~
~~Lec15 人工智能算法没讲，略过~~
Lec16 P/NP主要是规约分析√
Lec17 近似算法可以√

关于我提到的“3x2”

edit time: 2025-12-15 13:21:02

算法理解的框架是：直觉 + 过程案例 + 伪代码 及其追问。

对于直觉，我们要追问：

这个直觉适用于什么上下文？复杂度如何？
在这个上下文中，如果不使用这个直觉，最简化或暴力的方式是什么？

对于过程案例，我们要追问：

边界条件的执行过程如何？换一个过程你还能写出来吗？
在这个过程中，最不显然的是哪个点，比如某个变量含义的设置？

对于伪代码，我们要追问：

递归或循环的循环不变量是什么？
如何向不懂算法的人解释清楚这个算法的过程？

Lec1 简单排序

插入排序

直觉：我们可以把新的元素插入已排好序的序列的合理位置，使得有序序列长度增加。

追问略去. 复杂度为 $\Theta(n^2)$ 。
过程：以31 41 59 26 41 58为例，
循环不变量：i记录有序段的长度，a[i]是待排序元素，迭代前有序段已有序，迭代后有序段有序、且长度加一。

伪代码：
找到a[i]应该放置的位置，给它腾出空间，将它放置于此.

// 设数组长度为n, 下标从0到n-1.

for i = 1 to n - 1: // 已有序的元素数量
	x = a[i] // 待排序元素
	找到位置j <= i, 使得a[j] <= x < a[j + 1]
	将a[j + 1]到a[i]向后移动.
	a[j + 1] = x

归并排序

直觉：我们可以设置两个指针，将两个有序段合并成一个有序段。每次合并是 $O(n)$ 的。
与此同时，为了减少合并次数，我们可以将数组二分，合并次数是 $O(\log n)$ 。

追问：什么是低效的合并？比如一个有序段每次只和一个元素合并，这样的合并次数是 $O(n)$ 。甚至有点像插入排序了。
过程：（子数组长度为1,2,4,8）
追问：一定要考虑边界条件。对于原数组长度为1时，已自动有序，不需要找子数组。除此之外，二分并不保证两个数组长度严格相等，且我们在合并迭代过程中事实上需要处理数组长度不相等的情况。对于其中一个子数组长度为0时，我们不需要做比较，而是直接把另一个子数组的所有元素依序添加到合并数组最后即可。
伪代码：

MergeSort(A, l, r):
	if (l == r) return;
	mid = (l + r) / 2;
	MergeSort(l, mid); MergeSort(mid + 1, r);
	Merge(A, l, mid, mid + 1, r);
	
Merge(A, l, mid, mid + 1, r) {
	// 初始化临时数组B, 长度与A相同
	i = l, j = mid + 1, k = 0; // 指向：两个子数组未遍历的第1个元素, 和B数组可以插入的位置
	while (i <= mid && j <= r) {
		if (A[i] <= A[j]) B[k] = A[i++];
		else B[k] = A[j++];
	}
	// 将B拷贝回A
}

循环不变量：递归和循环都要考虑不变量。
- 在本次递归前，两个子数组一定有序。从而我们只要各自从前往后遍历取更小的元素添加到新的数组后面，新的数组一定仍然是有序的，而不会因为子数组不是有序出现破坏新数组有序的情况。这一循环不变量还意味着，我们应该把子函数调用写在合并过程前面，从而先排长度更短的数组。
- 在每次循环迭代前后，新数组一定有序，指针i, j, k分别指向两个子数组的未排序位置和新数组有序段的下一个位置。在循环迭代后，新数组长度+1，两个子数组总共的未排序长度-1，新数组仍然有序，指针仍然指向相同性质的位置。

Lec2 分治

二分查找

直觉：我们可以通过每一次迭代时的信息，排除掉数组中一部分不满足性质的段，只在满足性质的段中查找所需元素。

上下文：有序，或者更深刻地：当前元素的左半部分或右半部分满足某一性质，另一半部分不满足。
暴力：从前往后或从后往前，需要判断所有元素所以 $\Theta(n)$ ，但我们二分的话只需要判断 $\Theta(\log n)$ 的元素。
过程：
边界：当待判断元素恰等于所求元素时，则已找到。当待判断区间长度为0还是找不到时（这是一定存在的，因为二分并不严格保证两个子区间长度相同），则不存在。
关键：通过判断，只执行左半或右半子函数，或者修改循环边界点。
伪代码：

// 假如A是升序的, 我们要找到元素x所在的位置.

BSEARCH(A, l, r, x) {
	if (l > r) return -1; // 区间长度小于1, 注意l==r时闭区间长度为1
	
	mid = (l + r) / 2;
	if (A[mid] == x) return mid;
	else if (A[mid] < x) return BSEARCH(A, mid + 1, r, x);
	else return BSEARCH(A, l, mid - 1, x);
}

循环不变量：递归前后待查找元素一定位于当前待判断的区间、或可以通过判断当前区间来确定待查找元素不存在。我们先
描述：因为是有序序列，我们通过判断当前元素、可以确定当前元素及左边或右边都满足某一性质。

快速排序

写着写着突然反应过来了这个直觉。好玩。开心。
edit time: 2025-12-15 14:00:51

直觉：当每个元素的左侧都小于等于它、右侧都大于它时，则整个数组已有序。 即我们由长到短进行“划分”，当我们划分区间长度为1或0时，则整个数组已有序。

复杂度：每次选一个划分点、把其余元素放到左边和右边是 $O(n)$ 的。当我们选择元素作为划分点这件事需要对所有元素执行时，则快速排序退化为 $O(n^2)$ 。当我们选择元素作为划分点这件事只需要对一个元素执行时（原数组已有序），则快速排序进化为 $O(n)$ 。一般地，不严谨地讨论，当我们随机地选择划分点时，左右两侧的区间长度是基本相等的，那么我们总共需要选择 $O(\log n)$ 次划分点，也就是一般的复杂度为 $O(n \log n)$ 。
上下文：排序就不说了，大家伙都清楚。
过程：下述是对数组长度为8的划分过程，后续还要对子区间依次执行划分过程才能完成整个排序。
边界：前述复杂度已讨论。
关键：维护小于等于的段和大于的段。除此之外，我们先对大的区间进行划分、再对两个子区间进行划分。
伪代码：
循环不变量：
- 循环：划分点左侧的区间都小于等于划分元素，右侧都大于划分元素。
- 递归：每个子区间，它左边的子区间一定小于等于它，右边一定大于它。
描述：我们把原数组划分为几个段，每次迭代前后维护这几个段的性质。第一个段是小于等于划分元素的段，第二个段是大于等于划分元素的段，其余部分是未排序的段。我们每次迭代从未排序的段取出元素加入两个段中，最后把划分元素置于两个段之间。

矩阵乘法

先讲解朴素分治，后面再优化到Strassen算法等。

以下为了节省自己的工作量，文字部分由ai编写。

直觉：我们可以将大矩阵分解为小块进行乘法，减少单次乘法的规模，利用递归实现。

根据下述过程，设 $n \times n$ 的矩阵乘法的代价为 $T(n)$ ，则根据计算1次矩阵乘法需要计算8次子矩阵乘法，有 $T(n)=8T(n/2)+\Theta(n)$ 。求得为 $O(n^3)$ 。但它为后续的优化算法（如Strassen算法， $O(n^{2.81})$ ）提供了基础框架。
暴力方式是三重循环直接计算 $C[i][j] = \sum_{k=1}^{n} A[i][k] \cdot B[k][j]$ ， $O(n^3)$ 。

过程：矩阵乘法的分块计算。（核心！！）

边界条件是当矩阵大小为 $1 \times 1$ 时，递归终止，直接返回两个数的乘积。如果尝试用分治处理非2的幂次维度，需要进行填充或特殊处理子矩阵大小。
先解决小的矩阵，再解决大的矩阵。所以递归调用写在把矩阵组合起来的前面。

伪代码：

MatrixMultiply(A, B, n):
    if n == 1:
        return A[0][0] * B[0][0]
    
    将A划分为四个 n/2 × n/2 的子矩阵: A11, A12, A21, A22
    将B划分为四个 n/2 × n/2 的子矩阵: B11, B12, B21, B22
    
    C11 = MatrixMultiply(A11, B11, n/2) + MatrixMultiply(A12, B21, n/2)
    C12 = MatrixMultiply(A11, B12, n/2) + MatrixMultiply(A12, B22, n/2)
    C21 = MatrixMultiply(A21, B11, n/2) + MatrixMultiply(A22, B21, n/2)
    C22 = MatrixMultiply(A21, B12, n/2) + MatrixMultiply(A22, B22, n/2)
    // 总计8次矩阵乘法
    
    将C11, C12, C21, C22组合成 n×n 矩阵C
    return C

循环不变量：

每次迭代前，先进行划分，四个子块未完成计算。迭代后，四个子块均完成计算，可以直接合并成为结果块。 返回的矩阵大小和两个输入矩阵大小相等。

Strassen算法：
之前的矩阵乘法的分块计算需要8次矩阵乘法。Strassen算法通过一些巧妙的方式，只需要7次矩阵乘法。~~怎么直觉感觉是信息压缩和共享~~

多项式乘法

包括朴素分治、Karatsuba算法、FFT。
讲得并不仔细。

直觉：利用多项式的点值表示法（一组 $(x, y)$ 点）进行乘法比系数表示法（ $a_0 + a_1x + \dots$ ）更高效，因为点值乘法只需 $O(n)$ 时间（对应点 $y$ 值相乘）。
而多项式在复数域上是一定可以分解为点值表示法的，进而我们先转换为点值表示法、利用点值表示法进行乘积、再转回原多项式形式。

过程：计算 $(x^2 + 3x + 2)(x^2 + 6x + 5)$ ，如果拆开乘是 $\Theta(n^2)$ 的，而如果转为点值表示法则可以快速得到 $(x+1)^2(x+2)(x+5)$ 、再转回原多项式形式即可。

朴素分治： $T(n)=4T(n/2)+\Theta(n)$ ，解得是 $\Theta(n^2)$ 的，与拆开乘复杂度相同。

Karatsuba算法：解得是 $\Theta(n^{\log_2 3})$ 的。有所提升。

FFT（快速傅里叶变换）：在复数域上分解多项式。
记n项的多项式 $A(x)$ （最高次数为 $n-1$ ，最低次数为 $0$ ）是 $n-1$ 次多项式，
两个 $n-1$ 次多项式乘积是 $2n - 2$ 次多项式，也就是 $2n-1$ 项。

注意上面这个定义。

为了确定一个 $2n-1$ 项的多项式，我们需要为它采样 $2n-1$ 个点，这 $2n-1$ 个点是在两个原多项式中各采样 $2n-1$ 个点，然后再把它们乘到一起得到的。

ps. 注意原多项式可以采样任意多个点（就像在直线上有无穷多个点），但只要 $n-1$ 个点就可以确定原多项式（就像两点就能确定一条直线y=kx+b，它的次数 $n-1=1$ ，项数为 $2$ ）。

整理一下，FFT分为三步：
在两个多项式各自采样 $2n-1$ 个点，这一步进行了很大的优化，从 $O(n^2)$ 变成了 $O(n \log n)$ 。
将这 $2n-1$ 个点乘在一起是 $\Theta (n)$ 的。

如何 $O(n \log n)$ 地采样 $2n-1$ 个点？

关键注意：我们通过计算两个子过程 $A_{even}$ ，获得了原过程 $A$ 的两个点。这是非常amazing的。

Lec3 比较算法与随机化

堆排序

非常易错：建立堆是 $O(n)$ 的。
而每次更新是 $O(\log n)$ 的。

直觉：先建立大根堆，然后每次从堆中排出一个元素，这样形成的一个序列是升序的。

建立大根堆是 $O(n)$ 的，下述会证明。每次从堆中排出一个元素时，不妨把它与数组末尾的元素交换，则一次交换和一次维护堆的过程是 $O(\log n)$ 的，故堆排序是 $O(n \log n)$ 的。
关于建立大根堆是 $O(n)$ 的，我们可能会不严谨地想：对于一个数组，把后半作为叶子元素，然后对前 $n/2$ 个元素执行维护操作，而维护操作是 $O(\log n)$ 的，故这一操作应该有个上界 $O(n \log n)$ 。但通过严格分析，我们发现不同高度的维护代价是不同的：对于某个特定的 $h$ ，维护操作是 $O(h)$ 的，高度为 $h$ 的节点数为 $n/2^{h+1}$ ， $h$ 的取值范围是 $0$ 到 $\log n$ 。 这样求和之后即得 $O(n)$ 。

上面这一处建立大根堆是 $O(n)$ 的分析比较重要！

过程：

维护大根堆

边界条件：当一个元素为叶子元素、或者子元素都比它小时，交换结束。
对于大根堆，一个小的元素是往远离根的方向逐层下降的。其实是在树上进行一个有序链表的元素插入，挨个交换腾挪即可。

建立大根堆

一定要注意是自底向上建立，见下述循环不变量的讨论。

伪代码：

BUILD_MAXHEAP(A, n) {
	for i from n/2 to 1 {
		HEAPIFY(A, n, i);
	}
}

HEAPIFY(A, n, i) {
	if (i >= n/2) return; // 叶子节点不必维护
	
	max_child = 2i;
	if (A[2i] < A[2i + 1]) max_child = 2i + 1;
	
	if (A[i] < A[max_child]) swap(A[i], A[max_child]);
	else return;
}

循环不变量：
- 对于维护操作，当前元素之上的元素链一定与它组成了递减序列，而当前元素之下尚未维护。在每次交换后，递减序列长度+1。也可以从另一个角度认识：当前元素的父元素一定满足父大于子的性质，而在完成一次交换之后，交换前的位置也满足父大于子的性质。
- 对于建堆操作，由于我们维护时对叶子元素不做任何处理，因此可以直接将原数组的后n/2个元素作为叶子元素（已知结论：完全二叉树的叶子元素数约为n/2），从第 n/2 元素开始、一直到第1个元素这样自底向上地建立。这是因为n/2元素之后因为我们把它们作为叶节点，已经默认满足了“被维护过”的性质，而我们按照自底向上的顺序建立，不会破坏上面的元素未被维护、下面的元素已被维护这个循环不变量，使得完成维护的元素逐渐增加。

随机快速排序、随机快速选择

随机快速排序和随机快速选择的分析，参见【知识】数学部分的Lec3指示器随机变量部分。

中位数的中位数算法

这个算法很神奇。它在寻找Top-K时最坏情况是 $O(n)$ 的。
（我们之前的随机快速选择都只是 $O(n \log n)$ 。）

我们先从结果得到的递归式直观地感觉一下它得到的是 $O(n)$ 。
$T(n)=T(n/5)+T(7n/10)+O(n)$
两个子问题加起来不到 $n$ ，我们从【知识】数学部分的Lec2 递归方程求解那里就能直观感觉到，这玩意最坏应该是 $O(n)$ 的。这里给了一个简单的尝试法证明。

接下来稍微详细地看看这个东西的直觉。
如果希望深入一些细节，请参见： BFPRT——Top k问题的终极解法 - 知乎

SELECT函数过程：（ $T(n)$ ）

我们将n个元素分成5个一组的约n/5个组。在每个5个一组中，我们使用直接插入排序，找到中位数（黄色）。
对这些约n/5个中位数执行SELECT函数，得到中位数的中位数 $x$ （红色）。（ $T(n/5)$ ）
如果 $x$ 就是要找的 top-k ，则停止。否则大于等于 $x$ 的元素至少有 $3n/10$ 个，小于等于 $x$ 的元素也至少有 $3n/10$ 个。我们只会排除掉这二者中的一部分，在剩下至多 $7n/10$ 个元素中执行SELECT函数，继续下去。（ $T(7n/10)$ ）
上述这样的过程是 $T(n)=T(n/5)+T(7n/10)+O(n)$ 的。

顺序统计量和top-k问题总结

总结

（感谢DeepSeek撰稿。
本部分总结与后述“练习”里提到的“前k个”问题互为补充。）

以下是对三种算法解决Top-K问题的复杂度比较表格：

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	适用场景
直接排序并取第k个	O(n log n)	O(n log n)	O(1) 或 O(n)（取决于是否原地排序）	数据量较小或已接近有序
快速选择（QuickSelect）	O(n)	O(n²)	O(1)（迭代版本）或 O(log n)（递归版本，栈空间）	数据随机分布，不需要保证最坏情况
中位数的中位数（BFPRT）	O(n)	O(n)	O(n) 或 O(log n)（取决于实现）	需要严格保证线性最坏时间复杂度

补充说明：

直接排序：
- 例如使用快速排序、归并排序等，然后直接取第k个元素。
- 时间复杂度稳定为 O(n log n)，但可能比某些 O(n) 算法更简单。
快速选择：
- 基于快速排序的划分思想，每次丢弃一部分数据。
- 平均 O(n)，但最坏情况（如已排序数组）会退化到 O(n²)。
- 可通过随机化选择pivot来避免最坏情况（期望线性时间）。
中位数的中位数（BFPRT算法）：
- 通过精心选择pivot（每5个一组取中位数，再取中位数的中位数）保证每次划分至少淘汰 30% 的数据。
- 最坏情况下严格 O(n)，但常数较大，实践中可能比随机化快速选择慢。
- 常用于对时间敏感且需要保证最坏情况性能的场景（如实时系统）。

如果数据量不大或实现简单优先 → 直接排序。
如果数据随机分布且追求平均性能 → 快速选择（可随机化pivot）。
如果需要严格保证线性最坏时间复杂度 → 中位数的中位数（BFPRT）。

练习

要基于比较找到前k个最大元素并使其排列好。
这个用处太广泛了。事实上是为了比较排序、优先队列、“中位数的中位数”这几种算法。

a. 使用归并排序，它的最坏情况是 $\Theta(n \lg n)$ 。（不能使用快速排序或随机快速排序是因为它的最坏情况是 $\Theta(n^2)$ ，而后者仍存在最坏情况，只是期望复杂度是 $\Theta(n \lg n)$ ）。
然后再遍历取出前 $i$ 个最大数，这是 $\Theta(i)$ 的。
综上，运行时间是 $\Theta(n \lg n + i)$ 。

b. 建堆是 $\Theta(n)$ 的（一定要注意！这个还挺反直觉的，我在相关章节专门提过），
从堆中取出一次最大元素是 $\Theta(\lg n)$ 的，执行 $i$ 次。
故为 $\Theta(n + i \lg n)$ 。

c. 这里的顺序统计量算法即找到第k大的元素，可以使用快速选择算法（平均 $\Theta(n)$ ，最坏 $\Theta(n^2)$ ）、或者BFPRT（中位数的中位数）算法（最坏 $\Theta(n)$ ）。为了最佳复杂度，这里选择后者。
后者就是划分成5个一组、插入排序找中位数、然后找中位数的中位数之类的那个算法，在算法导论中有所介绍。（BFPRT——Top k问题的终极解法 - 知乎）
划分是 $\Theta(n)$ 的，扫一遍、把小于的放左边、大于的放右边就行。
然后对前 $i$ 大的数执行归并排序，最坏是 $\Theta(i \lg i)$ 的。
总之，最坏是 $\Theta(n+i\lg i)$ 。

Lec6 动态规划太能用这个结构讲了，来讲讲讲讲

动态规划是为了解决分治中的重叠子问题引入的，通过记录子问题的解、或者优先计算子问题，来解决分治问题。要求问题的最优解由子问题的最优解组成。
可以从以下角度思考：
(1) 转移变量。某个变量是从少往多计算、能够产生转移关系的吗？（“重叠子问题”）
(2) 选择（变量）。在做出选择后，原问题拆分成一个或多个子问题。为了计算函数，往往需要遍历选择变量，并且只选择其中的某一个特定值。
(3) 函数定义。函数有哪些变量根据(1)决定，函数的定义方式和初值条件由问题决定，函数的递推由(2)确定。
~~哇我这3点总结得太精辟了~~
edit time: 2025-12-23 11:10:36

最优二分查找树

“做的选择”是以某个节点为根节点，即选择变量为 $k$ 。
设区间 $[i,j]$ 的最优平均比较次数为 $m[i,j]$ 。

直觉：最优二分查找树由最优二分查找子树组成。

关键是符号定义。

最优二分查找树事实上形成了：
n个端点（概率记为 $b_i$ ，从1到n）和n+1段区间（概率记为 $a_i$ ，从0到n）。

递推过程：

记 $[i,j]$ 中所有概率之和为 $w[i,j]$ ，
结论：最终我们所求的是整个树的数值 $m[1,n]$ ，最优平均比较次数 $m[i,j]$ 满足：
(1) $m[i,i-1]=0$
(2) $m[i,j] = \min_k (m[i,k-1] + m[k+1,j] + w[i,j])$
因此，我们应该先从长度较短的区间开始，直到得到 $m[1,n]$ 。
区间的可能数为 $O(n^2)$ ， $k=O(n)$ ，故这一动态规划总复杂度为 $O(n^3)$ 。

伪代码

最长公共子序列 LCS

要求两个可能不等长的序列的最长公共子序列，注意不一定是最长连续元素。
设第一个序列到元素 $i$ ，第二个序列到元素 $j$ 的最长公共子序列长度为 $C[i,j]$ 。

直觉：最长公共子序列由去掉一个元素的最长公共子序列组成。可能是去掉第一个序列的最后一个元素，可能是去掉第二个，也可能是去掉两个的最后一个相同元素。
过程：是从左往右添加元素的过程，自底向上。（所以只需要用两个指针各自遍历两个序列即可，而不是“区间”。）

建表 O(mn)，需要把i和j的各种情况都算出来
追踪解 O(m+n)

假设少一个元素的两个序列（可能不等长！）的最长公共子序列已经计算出来了，我们要在它们之后各自添加一个元素。
如果这两个元素相同，则为最长公共子序列贡献一个元素（+1）。
如果这两个元素不同，其中仍然可能有一个元素能够为最长公共子序列贡献一个元素，需要把两个情况都取一下、取其最大值。

边界：两个序列中任一个长度为0时，最长公共子序列为0。
递推：
- $C[i,j]=C[i-1,j-1]+1,x[i]=y[j]$
- $C[i,j]=max(C[i-1,j],C[i,j-1]),x[i] \ne y[j]$

背包问题

原始背包问题没有每种物品的个数要求。
做的“选择”是拿或不拿。
记拿了前 $k$ 个物品（反映遍历顺序是从前往后），总重量不超过 $y$ （反映重量填表顺序是从轻到重）的最大价值是 $F[k][y]$ 。

直觉

如果我们要追踪最终得到的解（选了哪些物品），只要建立一个指示变量 $i[k][y]$ ，看每次 $F$ 选了还是没选即可。

过程

伪代码

投资问题

需要区分选择变量和转移变量。
在投资问题中，投资前 $k$ 项、投入资金不超过 $x$ 是转移变量，前后具有转移性，
但是在第k个投入 $x_k$ 是选择变量， $x_k$ 之间互相没有依赖和转移，我们只能选择其中的某一个特定值。
定义 $f(k, x_k)$ 或者 $f_k(x)$ 是将𝑥元投入第i个项目的收益，最大收益为 $F_k(x)$ 。

直觉：对k做转移，对 $x_k$ 做选择，总钱数不超过 $x$ 。 $O(nm^2)$ ， $m$ 行 $n$ 列。
$F_k(x)=\max_{0 \le x_k \le x} (f_k(x_k) + F_k(x-x_k))$

过程：

带权重的区间调度

新的任务是在已有的最大区间调度基础上添加的。
则如果能够添加新的任务，已有的最大区间调度结尾一定在新的任务前或正好相连。

转移变量：检查的区间序号 $i$ ，先排序，然后从前往后检查。
选择：添加新的任务或不添加。
函数：当前最大区间调度的区间总权重 $OPT[i]$ 。

直觉： $O(n \log n)$ ，因为这个递推是 $O(n)$ 的，找 $p(i)$ 需要先 $O(n \log n)$ 排序。

$OPT(i) = max(OPT(i-1)，OPT(p(i)) + w_i)$
其中 $p(i)$ 是在任务 $i$ 之前的所有任务里面离 $i$ 最近并且兼容的活动。
（如果没有兼容的活动，则 $𝑝(i) = 0$ ）

过程：

伪代码：

连写分数

这个题目约束设置有点绕，需要稍微读读题。
放在一群算法导论的经典问题里还是稍微有点难了。

转移变量：数字串处理完前 $i$ 个字符，特殊题目处理完 $mask$ 。
ps. 转移变量只要“多“的能从”少“的得到即可。 $mask$ 是第一次用，这个设置是因为我们可能跳着挑选特殊题目，我们挑选哪些特殊题目最少也得用一个二进制01串进行记录。但是前 $i$ 个字符我们就只需要记录一个边界 $i$ 即可。
选择和选择变量：
切分边界 $j$ ， $s[j:i-1]$ 为整个数字， $j$ 之前的作为子问题。
普通题不改 $mask$ ，特殊题要改 $mask$ 。

直觉：

矩阵链乘法

要求 $A_1 \dots A_n$ 的矩阵链乘法。我们把问题建模成要求 $A_i \dots A_j$ 的矩阵乘法，并且记录矩阵维度是 $P_0 \dots P_n$ ，矩阵 $A_i$ 的维度是 $P_{i-1} \times P_i$ 。 （注意左边小一个！）
转移变量：边界 $i$ 和 $j$ 。
选择变量：切分点 $k$ ，使得 $A_i \dots A_j$ 拆分为 $A_i \dots A_k$ 和 $A_{k+1} \dots A_j$ 两个子问题。即是最后一次矩阵相乘的发生位置。
函数定义： $A_i \dots A_j$ 的最少乘法次数。

直觉（递推）

要把 $A_i \dots A_k$ （ $P_{i-1} \times P_{k}$ ）和 $A_{k+1} \dots A_j$ （ $P_k \times P_j$ ）乘起来，需要进行的乘法次数是 $P_{i-1}P_{k}P_{j}$ 。注意左边界是 $i-1$ ！
因此有以下递推公式：

过程

伪代码
对于上述问题，
我们可以递归实现（自顶向下），空间小、时间大 $O(2^n)$ （因为会重复计算相同子问题）；
也可以迭代实现（自底向上），空间大、时间小 $O(n^3)$ （因为重复子问题可以查表）。

活动选择问题

$O(n^3)$ 。更好的贪心算法（见Lec7 贪心及其证明）是 $O(n \log n)$ 的。
想法很简单，转移变量是左右边界，然后选择变量是中间的切分点，dp变量设这一段区间最多的活动数，然后追踪一下解就得到了。很容易看出来是 $O(n^3)$ 的。

Lec7 贪心及其证明

证明：
思路(1) 归纳。把贪心得到的解与最优解用剪切-粘贴方法进行比较。
思路(2) 交换。分析最优解“逆序”的地方。因为贪心得到的解一定是根据贪心策略从小到大排序的。

活动选择问题

贪心策略：选择结束最早且相容的活动。
直觉：最大化所选活动结束后剩余的时间，供其他活动使用。
证明：如果最优解选了别的，可以把它替换成结束最早且相容的活动，不会减少*可选的后续活动数，重复替换即可得到相同大小的解。所以贪心最优。

上下文

$O(n \log n)+O(n)=O(n)$

证明

把上述的copy-and-paste表述成数学归纳法证明过程：

说人话：
假设最优解选到的第一个不满足贪心的是 $j$ ，把它替换成贪心得到的 $i_{k+1}$ ，不影响。

关于动态规划解法，见Lec6 动态规划部分。

最优装载问题

很容易想到，
贪心策略：取最轻的集装箱。
证明：
(1) 基础，如果只有一个集装箱， $w_1 \le C$ ，显然贪心最优。
(2) 归纳，设 $k$ 个装箱贪心最优。对于 $k+1$ 个装箱，设贪心得到的序列是 $w_1 \le w_2 \le \dots \le w_{n+1}$ ，另设最优解得到的装箱集合是 $O_{n+1}$ 。
取 $w_1$ 对应的箱子，若 $w_1 \in O_{n+1}$ ， $O_{n+1} - \{w_1\}$ 贪心最优，则整体最优。

对于归纳，可以打个比方：
贪心装了 {1,2,3,5} （下标，不是重量），最优解是 {1,2,3,4}
如果1（同时在两个集合中）是重量最小的，我们在最优解中把它干掉变成k个装箱{2,3,4}，贪心最优，而把1加回去正是最优解，所以由k个装箱贪心最优得到了k+1个装箱贪心最优。
如果5是重量最小的，不在最优解中。我们把最优解中重量最小的（比如4）那个替换成5，因为贪心一定取最轻的，所以贪心取到的这个集装箱一定重量不大于最优解中重量最小的集装箱，从而仍为最优解。
综上。

最小延迟调度问题

注意问题要求不是总延迟最小，
而是所有的延迟中最大的延迟最小。

贪心策略：先做ddl最早的问题。
证明：
假设最优解中有两个问题逆序。将它们交换过来，它们之中延迟最大的那个问题是交换前后四个延迟中最大的。即交换后仍为最优解。

符号：
设 $f(i)$ 是我们所求的要调度的任务 $i$ 的开始时间，问题就是求最优的 $f$ 。
给定的 $d_i$ 是任务 $i$ 的ddl， $t_i$ 是任务 $i$ 的服务时长，
延迟是实际的服务完成时间 $f(i)+t_i$ 减去要求的服务完成时间 $d_i$ 。

说人话：
假设i的ddl更迟但是先做了，即 $d_i > d_j$ 且 $f(i) < f(j)$ 。（延迟是实际完成时间减去要求完成时间）

交换前：
设 $i$ 的开始时间 $f(i)=s$ ，则此时 $i$ 的实际完成时间为 $s+t_i$ ， $j$ 的开始时间 $f(j)$ 也为 $s+t_i$ ， $j$ 的实际完成时间为 $s+t_i+t_j$ 。
此时， $i$ 的延迟是 $s+t_i-d_i$ ， $j$ 的延迟是 $L_{max} = s+t_i+t_j-d_j$ 。（容易由 $d_i>d_j$ 得到 $j$ 的延迟更大）

交换后：
$i$ 的延迟是 $s+t_j+t_i-d_i$ ， $j$ 的延迟是 $s + t_j - d_j$ ，我们可以证明这两个延迟都小于 $L_{max}$ 。
故经过上述交换，所有的延迟中最大的延迟没有变得更大，原来的最优解仍为最优解。

哈夫曼编码

贪心策略：每次取两个权值最小的节点进行合并。

证明：这里几个引理比较漂亮且并不平凡。
(引理1) 对于两个频率最小的节点，它们一定位于树最深的位置，且它们恰好是两个兄弟叶子节点。
(引理2) 将两个兄弟叶子节点的频率 $f(x)$ 和 $f(y)$ 加到一起、作为它们的父节点的频率（称为合并操作）。则总的权值 $B$ （频率*深度的求和）减少 $f(x)+f(y)$ 。

(证明) 先对k个元素进行归纳。
当k+1时，如果 $T_贪$ 不是最优的，反设存在更优的树 $T_优$ ，即有 $B(T_贪) < B(T_优)$ 。

把 $T_贪$ 两个频率最小的节点（记为 $x$ 和 $y$ ）进行合并，得到的树 $T_贪'$ 满足 $B(T_贪')=B(T_贪)-f(x)-f(y)$ ，且根据归纳假设， $T_贪'$ 是最优的。
把 $T_优$ 的 $x$ 和 $y$ 两个节点进行合并，得到的树 $T_优'$ 满足 $B(T_优')=B(T_优)-f(x)-f(y)$ ，且根据归纳假设， $T_优'$ 是最优的。

但是， $T_贪'$ 是最优的且 $T_优'$ 是最优的可得 $B(T_贪')=B(T_优')$ ，则有 $B(T_贪)=B(T_优)$ ，与我们的反设矛盾。

最小生成树 MST

Prim算法：从已选集合 $S$ 开始，选择连接 $S$ 与 $V-S$ 的最短边。 $O(n^2)$
Kruskal算法：如果加入最短边后不构成回路，则加入。 $O(m\log m)$
Prim证明：对最优解copy-and-paste。

Kruskal

这个麻烦一点，看看图上怎么归纳的（设G是顶点数为n+1的图）。
首先短接图 $G$ 的边 $e$ ，得到 $G'$ ， $G'$ 比 $G$ 少一个顶点，可以得到最小生成树 $T'$ ，然后对 $T'$ 执行短接的逆运算放回边 $e$ ，得到G的一个生成树 $T$ ，后续证明 $T$ 是 $G$ 的最小生成树。

短接即是选取边 $e = (i,j)$ ，替换为点 $k$ ，将连到 $i$ 或 $j$ 上的边全部连到 $k$ 上。
逆运算即是对点 $k$ ，替换为边 $e=(i,j)$ ，将连到 $k$ 上面的边任意地连到 $i$ 或 $j$ 上。

下述证明 $T$ 是 $G$ 的最小生成树。

Prim

Lec9 最短路径

关键是松弛操作。
当 $d[j] > d[i] + w(i,j)$ 时，执行松弛 $d[j] \leftarrow d[i] + w(i,j)$ 。

单源最短路径：

无负权：Dijkstra $|V|*ExtractMin+|E|*Relax$ ，数组是 $|V|^2$ ，堆是 $(|V|+|E|)\log|V|$

无权：BFS， $O(|V|+|E|)$

有负权：Bellman-Ford $O(|V||E|)$ 对一个源
多到多最短路径：

无负权：Floyd-Warshall $O(|V|^3)$

有负权：Johnson $O(|V||E|\log |V|)$

Dijkstra算法

extract_min和relaxation循环。

从还没确定的点里找一个距离最小的u，
把u加入S，并用u去“松弛”它的邻居。

Bellman-Ford算法

对所有边执行n-1次松弛操作，n是点数 $|V|$ ，得到全部最短距离。
再执行第n次松弛操作，如果最短距离仍能更新，则存在负权环。
（正确性分析原理：图中最长的简单路径长度为 $|V|-1$ 。）
解决负权环的问题， $O(|V||E|)$ 。

下图起点为A，希望得到最终到所有点的最短距离，并且存在负权边。

Floyd-Warshall算法

求解所有点到所有点的最短距离。
方法是任取两个点，以所有点为可能的中介点，执行松弛操作。

Johnson算法

解决Floyd-Warshall算法的负权问题。
思路：
1. 添加源点，到所有边连一条，使用Bellman-Ford算法求得 $h$
类比重力势能：取一个势能零点
2. 得到新的边权，在所有顶点使用Dijkstra算法求得最短距离 $\delta_h$
2. 将新的最短距离转化为原来的最短距离 $\delta$

原来的边权是 $w(u,v)$
新的边权是 $w'(u,v)=w(u,v)+h(u)+h(v)$

差分约束系统

Bellman-Ford在满足 $d[j] > d[i] + w(i,j)$ 时会执行松弛（ $d[j] \leftarrow d[i] + w(i,j)$ ），
因此最终得到的全部最短距离一定满足 $d[j] \le d[i] + w(i,j)$ ，
这恰好与我们要求解的 $x_i-x_j \le b$ 形式相同。

TODO

Lec10 网络流

把多个子分配（及其约束）给汇总起来，
让汇总最大，
从而得到分开的子分配的方案。

Edmonds-Karp：BFS建分层图（ $O(|E|)$ ），完成所有增广（ $O(|V||E|)$ ）。 $O(|V||E|^2)$
Dinic：BFS建分层图（ $O(|E|)$ ）、DFS找阻塞流（ $O(|V||E|)$ ），循环 $|V|$ 次。 $O(|V|^2|E|)$

这一章只讲了几个用来解网络流的算法，没有讲怎么把问题建模成网络流问题。
所以自己补了点例题。
[[网络流与建模问题.pdf]]

例1：二分图匹配 → 最大流

问题：有3个程序员（A,B,C）和3个项目（X,Y,Z），每个程序员能做的项目有限：

A能做X,Y
B能做Y
C能做X,Z
问最多能分配几个项目（一人做一个项目）？
建模：

源点→每个程序员（容量1）
程序员→他能做的项目（容量1）
每个项目→汇点（容量1）
为什么对：
流从源到程序员=1表示选中该程序员，流到项目=1表示项目被分配，项目到汇点=1表示项目只被一人做。
最大流值 = 最大匹配数。

例2：多源多汇 → 单源单汇

问题：多个水厂给多个小区供水，水管网络已知，问最大总供水量。
技巧：

加一个超级源点，连到每个水厂（容量=水厂产能）。
加一个超级汇点，每个小区连到它（容量=小区需求或无穷大）。
跑最大流。

例3：点容量问题 → 边容量

（作业里就有这个题）

问题：每个路口（节点）有通过人数上限，道路（边）也有容量，求从起点到终点最大人流。
技巧：把每个节点 $u$ 拆成 $u_{in}$ 和 $u_{out}$ ：

原进入 u 的边连到 uin。
uin→uout 边容量 = 节点容量。
原离开 u 的边从 uout 出发。

例4：最小路径覆盖（DAG）

问题：有向无环图中，选择最少的路径，覆盖所有顶点（每个顶点恰好在一条路径中）。
建模：

每个点 u 拆成 ux（左）和 uy（右）。
原边 u→v 变成 ux→vy（容量1）。
源点→所有 ux（容量1），所有 uy→汇点（容量1）。
最大匹配对应路径覆盖，答案 = 顶点数 - 最大匹配数。

举例：（参考网络流与建模问题 - 洛谷专栏）

像这样的一张图，最小路径覆盖
可以是 1→2,3→4，
可以是 1→3,2→4，
也可以是 1→2→4,3，
还可以是 1→3→4,2。
总共有四个这样的最小路径覆盖。

我们将原问题转换成了如下的最大流问题：

在这个问题中做最大流（每条边容量都为1），
我们找到的最大流使用的边包括：
$(1,2'),(2,4')$ ，即对应1→2→4,3，
$(1,3'),(2,4')$ ，即对应1→3,2→4，
等等。

例5：最小割的应用 — 项目取舍

之前讨论的都是最大流的建模。这里来一个最小割的建模。
“割值：付出的成本f + 没赚到的钱 (c的剩余量)”
[[网络流最小割的建模]]

问题：你要做几个项目，每个项目有收益，但需要租用一些设备。设备有租金。怎么选项目使（总收益-总租金）最大？
建模：

源点→每个项目（容量=项目收益）
每个项目→它需要的设备（容量=∞）
每个设备→汇点（容量=设备租金）
最小割的意义：
割左边（与源点同侧）的项目是要做的。
割右边（与汇点同侧）的项目是不做的。
割值 = 放弃的收益（右边项目收益）+ 付出的租金（左边项目用到的设备租金）。
总利润 = 总收益 - 割值 → 要使割值最小，就是最小割！

Lec11 回溯

可能因为过程中没有可选的选项而回溯，
也可能因为完成了整个解的构造而回溯。

从前往后依次做选择。如果做某个选择之后无法满足约束条件，则回退该选择。
做了选择之后需要记录当前状态，回退即是将当前状态改回到前一个状态、然后在选择集合中取另一个选择。

思路及伪代码：

构造当前解，直到到达叶子处。

在过程中，只在能够满足约束条件的选择集合中进行选择，如果选择集合为空但仍未到达叶子处，则回溯，尝试构造其他解。

如果成功到达叶子处，则当前解为一个可行解，计入可行解集合、或者比较最优解。然后回溯，尝试构造其他解。

多米诺性质

正确性是通过多米诺性质满足的：如果更深的满足某个性质，则比它浅的也满足。

n皇后

装载问题

思路：
尽可能往轮船1装最多重量的集装箱。如果其余的集装箱能够装入轮船2，则该解存在，否则不是有效解。
在直接暴力搜索（ $O(2^n)$ ）的基础上，

通过约束条件、把一些无法满足条件的解提前结束掉，回溯尝试构造其他解。

每个到达最深处的解都是有效解，构造出有效解后通过回溯尝试构造其他解。在本题目中我们要求有效解中的最优解。
每次做2个选择中的一个，共要做n次选择，仍然为 $O(2^n)$ 。

首先从大到小排序。
见下图，每个分支处即是是否选择当前第 $i$ 个货物。
如果选择，分支向左下延伸（ $x_i = 1$ ），记录当前增加权值。
如果不选择，分支向右下延伸（ $x_i = 0$ ），当前增加权值为0。

例如上图找到了第一个解 $(1,0,1,0,1,0,0)$ ，回溯即是找到最后一个 $1$ 的位置，然后把它改为 $0$ ，向下延伸，找到另一个解 $(1,0,1,0,0,1,1)$ 。

图的着色问题

先为图上所有顶点从1到n编号。
对于每个顶点，它可用的颜色为 $m$ 个，即有 $m$ 个子节点。但是该顶点的相邻顶点已经使用过的颜色不能再使用。

举例： $n=7,m=3$
三种颜色分别为1红、2蓝、3灰。
对于顶点1，它有3种选择。假定选择1红。
对于顶点2，它有2种选择。假定选择2蓝。
对于顶点3，它有2种选择。假定选择1红。
...
我们在过程中，如果没有可选的选项，则回溯。
对于该问题，只要找到第一个可行解即可。如果还要找其他的可行解，则在找到可行解后回溯、尝试其他选择。

Monte Carlo估计四皇后问题的搜索树节点个数

通过Monte Carlo方法，随机选择一条路径，得到节点数量。如此重复多次，将节点数进行概率平均。

分支限界法

“记录已有的最大值、估算未选择的上界，
如果未选择的上界不超过已有的最大值，则剪枝。”

回溯法	分支限界法
主要用于找所有可行解	主要用于找一个最优解
剪枝依据：约束条件（不可行才剪）	剪枝依据：约束条件 + 界函数（没希望更优就剪）
通常深度优先	可深度优先、广度优先、优先队列扩展
例子：N皇后、图着色所有方案	例子：背包最优解、TSP最短路径、最大团

看以下背包的例子。
每个物品的单位价值是价值/重量，例如 9/7 。
（节点中间不是分数线！！只是分割了一下！！）

我们先直观感受一下：黄色的节点是被分支限界剪掉的，蓝色的节点是被约束剪掉的，橙色的是最优解，绿色的是待扩展节点。
我们完全没有考虑过 $x_4$ ，而是直接在考虑完 $x_3$ 甚至 $x_2$ 就完成剪枝了。不像回溯要么得靠约束，要么一直得判断到叶子节点。

如果某个节点的界函数值 ≤ 当前界（即它最好也超不过已知最佳值），就剪枝（不再搜索它的子树）。

否则继续搜索。

详细地我们可以这么看：
一开始，估算能达到的价值上界是 10 * 9/7，因为重量为10， $x_1$ 单价为 9/7。
假如此时选择了 $x_1=1$ ，则能达到的价值上界是 9 + 3 * 5/4 ，因为剩余能用的重量是3，这里第二层要考虑的是 $x_2$ ，单价为 5/4。
假如此时选择了 $x_2=2$ ，重量超了。剪枝。
...
$x_1=1,x_2=0,x_3=1$ 是已有的最大价值，是12。
...
假如选择了 $x_1=1,x_2=0,x_3=0$ 看看行不行。价值上界是 9 + 3 * 1/2 ，都不到已有的最大价值12，所以不需要继续往下判断了。这就是分支限界利用界函数的剪枝。
还有一个更好的例子： $x_1=0,x_2=2$ ，这里都不用选择 $x_3$ 和 $x_4$ ，我们拿 $x_3$ 估算以下上界为 10 + 2 * 3/3 ，也就只是跟已有的最大价值12恰好相等。那就不用往下看了。

最大团

用分支限界求解最大团，用一个例子说清楚。

旅行商问题

分支限界。

在找最短推销路线的过程中，我们一边走一边算：“哪怕后面全都选最近的路，总长度至少是多少？”
如果这个“至少”已经比已知最短路线还长，就放弃当前路线，回头试别的。
这样避免傻傻地走完所有可能路线才比较。

这个好玩。
首先扫一遍所有节点，记录从该节点出发的边的最小长度。
例如下图对节点 $1,2,3,4$ ，要记录的权值即是 $4,2,7,2$ 。

界函数：已走过的长度 + 其余节点的最小长度之和。

例如：
对于路线 $<1,3,2>$ ，已走过的长度是9+13，其余要加的是节点2的2和节点4的2，也就是界函数 $L=9+13+2+2$ 。

连续邮资问题

注意问题是“如何设计面值”，使得连续邮资的区间达到最大。

直觉：“不能断档”：分支限界的界。
当你已经确定了前 i-1 种面值，且它们能连续贴到 $r_{i−1}$ 元时，
第 i 种面值 $x_i$ 不能超过 $r_{i−1}+1$ 。

Lec12 在线算法及竞争分析

滑雪问题、电梯问题、约会问题、缺页中断

一定要注意输入是一系列事件的序列。

竞争分析：分类讨论，和“最优解”比较。这里“最优解”甚至可以看到未来。
要求最坏情况：对抗构造。
$C_{opt}(s)$ ：最优算法的最小成本
$C_A(s)$ ：算法的成本
如果对于所有输入 $s$ 都有：
$C_A(s) \le k \cdot C_{opt}(s) + O(1)$ ，则称竞争比为 $k$ ，即 $k-$ 竞争。

滑雪问题（BLTN算法）

better late than never
注意输入是一个序列。
对于输入小的情况、一直选便宜的选择；
直到对于给定的输入、这个选择反倒比另一个选择贵时，立刻换用另一个选择。

虽然看起来很神奇，但是莫名地居然在上述竞争比指标下是最优解。

输入小于等于9：最优解，竞争比为1
输入大于等于10：竞争比为19/10<=2

一般地，设租赁rent价格为 $r$ ，购买purchase价格为 $p$ 。不妨设 $r | p$ 。
BLTN：在第 $p/r$ 次买，前 $p/r - 1$ 次租。
定理：BLTN的竞争比 <= 2-r/p。

竞争分析：
对于给定的序列，
次数小于等于p/r - 1次的时候是最优解，竞争比为1。
次数大于等于p/r次，最优花销是p（一开始就买），而我们花销是p+(p/r - 1)*r=2p-r。
所以竞争比小于等于 (2p-r)/p=2-r/p。

最优证明：没有确定的算法竞争比上界比BLTN更低。

假设我们的算法在滑雪x次之后购买，则成本 $C_A=xr+p$ 。不妨设输入是滑雪x+1次。直觉上，
如果买迟了、x大于等于BLTN的在第 $p/r$ 次买（ $x \ge p/r$ ），那么一定会此时多付了额外的租的价钱，竞争比就比2-r/p大了。多付一次，也就是至少为2。
严格地， $C_A=xr+p \ge 2p \ge 2p-r$ ， $C_{opt}=r$ ，则 $C_A/C_{opt} \ge 2-r/p$ 。

如果买早了、x小于等于在第 $p/r-1$ 次买，那么一定会此时多付了额外的买的价钱，竞争比至少比BLTN此时的1大。
买的价钱显著到竞争比直接大于等于2-r/p：因为我们多付的买的价钱太显著了，最优解表示明明可以一直租的。
严格地， $C_A=xr+p$ ， $C_{opt}=(x+1)r$ ，则 $C_A / C_{opt} = {{xr+p} \over {(x+1)r}}$ 。为了方便用 $x$ 放缩得到上界，分离一下变量，得到 $1+{{p-r} \over {xr+r}}$ ，放缩并化简得到 $C_A / C_{opt} \ge 2-r/p$ 。

电梯问题

对于给定的序列，
小于等于时，一直选便宜的选择（等）。大于时，立刻换用贵的选择（爬）。
设等电梯x秒。当x+E<=S时等，>时爬。
也就是BLTN：先等S-E秒，然后爬。

竞争比：
设电梯到达时间为y。
y+E<=S时，最优解和BLTN都是等着乘电梯，时间成本为y+E。竞争比为1。
y>S-E时，最优解是一开始就爬楼梯即时间成本为S，BLTN时间成本为(S-E)+S=2S-E，竞争比为2-E/S。
所以竞争比上界为2-E/S。

约会问题

我记得我在网上看到的什么面试算法是先把前面一些人挂掉，
后面如果碰到比前面挂掉的人优秀的就立刻录用

算法：总共n个人，挂掉前n/e个人，然后看是否有大于前n/e个的元素。
这个算法有1/e的概率选到最大元素。

选到最大元素的概率设为 $P$ 。
通过优化下述 $P(t)$ ，得出应该令 $t = {n \over e}$ ，此时 $P={1 \over e}$ 。

竞争分析：
此算法选择的要么是相对前t个人较好的人，要么是最后一个人。
最后一个人的排名是 $C_A=O(𝑛)$ ，不一定好。
对排名计算竞争比， $C_{opt}=1$ ，则竞争比为 $O(n)$ ，不好。

得出上述P的详细过程：

缺页中断

LRU

定理：设缓存大小为k，则LRU满足k-竞争。
证明：
将请求划分为不同“阶段”，每个阶段内有k个不同元素。
开启下一个新阶段，当且仅当当前阶段无法继续“处理”新请求：处理包括已存储该元素，或者通过替换上一阶段的元素来存储该元素。

确定性在线算法

定理：任何缓存大小为k的确定性在线算法的竞争比为Θ(𝑘)。
举例：缓存大小为3，请求为 1,2,3, 4,1,2, 3,4,1, 2,3,4 共12次。（在每一步，请求算法A不拥有的页面）
以LRU为例，可见12次请求有12次不命中。其余算法也可同理构造请求。

而理想的可以预知未来的算法，可以删除未来请求时间最远的页面。例如：

请求	请求时操作	操作后存储	备注
1	+1	<1>
2	+2	<1, 2>
3	+3	<1, 2, 3>
4	-3 +4	<1, 2, 4>	在未来, “3”请求最远
1		<1, 2, 4>
2		<1, 2, 4>
3	-2 +3	<1, 3, 4>	在未来, “2”请求最远
4		<1, 3, 4>
1		<1, 3, 4>
2	-1 +2	<2, 3, 4>	在未来, “1”请求最远
3		<2, 3, 4>
4		<2, 3, 4>

当离线算法删除一个页面时，下一个删除操作至少在k步之后发生。
例如上述删除3、删除2恰好差了k步。

故把开头的三个请求排除掉，后面稳定状态下，
$C_{opt} = m/k$ （例如9/3=3，因为每差3步删除一次，总共只需要这3次删除开销）
$C_A=m$ （例如9）
综上，竞争比 $C_A / C_{opt} \ge k$ 。

（ps. 关于“至少”，步数更多的可以找一个不均匀的序列。直觉上，由于我们对其他的元素多次命中，某个元素两次删除之间的间隔会拉得更长一些。上述案例没有体现“至少”，而是一个恰好为k的情况。）

随机标记算法

把构造最坏案例时“请求不在的页面”这个条件干掉了。

竞争分析练习

俩题都不是很好搞

习题1：来回倍增走路

该问题也称作奶牛-路径问题（Cow-Path Problem）或称“栅栏上的洞问题”。可以抽象成这样的数学描述：有一维数轴，其上有一个未知位置的目标；我们初始时位于数轴原点，可以左右（向数轴负向/正向）移动。该问题要求尽可能以最小的路程来找到这个目标。
由于所给出的信息仅有是否找到了目标；解决方案也比较容易想到，就是折返跑：首先从原点向右走出单位长度，随后返回原点，向左直至到达原点右侧两倍单位长度，如此反复，每次探索距原点的长度都加倍。这种策略叫做倍增（doubling）。

数学规划与运筹学 (14) 算法专题之在线算法 - 知乎

引理：使用倍增策略求解直线上的在线搜索问题是 9-竞争的。

证明：考虑最差的情况，设目标位于距离原点距离为 $n$ 的位置，且对某 $j \in \mathbb{N}$ 有
$2^j < n \leq 2^{j+1}$ ，那么倍增策略的前 $j$ 步都不会找到目标，此时共走的路程为 $2 \times \sum_{i=1}^{j} 2^i$ 。
（ $\times 2$ 是因为往返）。接下来的第 $j + 1$ 步，假定我们不幸选错了方向，于是在错误的方向上又走了 $2 \times 2^{j+1}$ 路程。接下来，我们向着正确的方向走了 $n$ 路程，终于找到了目标。算下来一共走的路程为
$2 \sum_{i=1}^{j+1} 2^i + n = 2(2^{j+2} - 1) + n \leq 8n - 2 + n \leq 9n$

而最优情况显然是 $n$ ，因此倍增方案是 9-竞争的。

可以证明，9 是最好的结果，没有其它算法的竞争比能比 9 更低；这一结论的证明较困难，请见 Baezayates, R. A., Culberson, J. C., & Rawlins, G. J. (1993). Searching in the plane. Information and computation,106(2), 234-252. 的 Theorem 2.1。

习题2：在线独立集

这道题相当绕。需要以下几个直觉：
一开始有n个点（1, 2, 3, ..., n)，I = {1, 2, 3, ..., n}。

如果出现的边两个点都在I中，至少需要删除其中一个点，保持独立集。
对抗构造的结果是，一开始就说是一棵n-1条边的树，结果也确实是一棵树，但是仍然让在线算法从n个点删得只剩下1个点了。
（如果对抗构造不好，可能给出的边两个端点不一定在当时的I里，不需要删点，这样的话n-1条边之后剩下的点会多一些）

对于任意的在线算法，对抗构造如下：
对抗者目标是让算法只剩下1个点，在线算法目标是剩下尽可能多的点。

对抗者举例如下（n=5）：

对抗者随意选两个点，比如 A_1=1 和 A_2=2，给边 (1,2)。算法必须删掉 1 或 2。假设算法删了 2，现在 I={1,3,4,5}。
对抗者选一个新点（还没参与过边的点），比如 3，给边 (1,3)。因为 1 还在 I 里，3 也在 I 里，所以算法必须删 1 或 3。假设算法删 3，则 I={1,4,5}。
对抗者发现算法总是保留 1，删掉新点。那么对抗者可以继续用同样的方式：给边 (1,4)、(1,5)，每次都逼算法删掉 4 或 5，算法如果总保留 1，最后 I={1}。这样就成功了：最终图是星形树，中心是 1，所有叶子 2,3,4,5 都被删掉了。算法最终只剩 1 个点。

如果在线算法改变选择会怎样？
假设在第 2 步，给边 (1,3) 时，算法删了 1（保留 3）。
那么 I={3,4,5}。
对抗者就记录：现在“中心”变成了 3。
下一步，给边 (3,4)，算法必须删 3 或 4。
如果删 4，中心还是 3；如果删 3，中心变成 4。

无论如何：

每个新点（第一次出现的边的一个端点）都会和当前的“中心”连边。
算法只能保留其中一个（中心或新点）。
一旦算法保留新点（删除旧中心），那新点就成为新的中心，对抗者之后就用它连下一个新点。
这样，整个过程中，任何时刻 I 中最多只有一个“中心点”能和所有后来的点相连，最后当所有点都加入图后，I 里最多只有最后保留下来的那个中心，其余点都会因为某条与中心的边而被删除。
所以最终 I 的大小 ≤ 1。

总之，上述的对抗构造，让任何的在线算法都只能剩1个点。
但是假如我们可以预知未来，一开始就知道对抗构造最终得到的树的所有边，树一定是二分图，所以可以只删二分图中点比较少的那部分。剩下的点数至少为n/2。
因此：
${OPT \over ALG} \ge {n/2 \over 1}={n \over 2}$ 。
即没有任何确定性算法能保证竞争比小于n/2得证。

Lec16 P和NP未完成

P是可以快速求解，
NP是Yes实例可以快速验证，
NP-hard是所有NP问题可规约到的问题，
又是NP又是NP-hard的是NP-complete

类别	定义	例子	是否可在多项式时间验证	是否可在多项式时间求解
P	可在多项式时间内求解的判定问题	最短路径、最小生成树、排序、二分查找	✓	✓
NP	可在多项式时间内验证一个解的正确性	布尔可满足性问题（SAT）、哈密顿回路、独立集、顶点覆盖、子集和	✓	未知（可能可以，可能不行）
NP-hard	至少和 NP 中最难的问题一样难（不一定是 NP 中的问题）	停机问题（不是 NP！）、旅行商问题（判定版）、最大团问题	不一定	否（除非 P=NP）
NP-complete	既是 NP 又是 NP-hard（NP 中最难的问题）	SAT、3-SAT、哈密顿回路、顶点覆盖、独立集、子集和、背包问题（判定版）	✓	否（除非 P=NP）

规约

说人话：一个问题的实例可以通过构造过程转换成另一个问题的实例，且这两个实例有解是等价的。

将实例转换到另一个实例

左有解等价于右有解

右有解等价于左有解

规约当然是传递的。
如果左边的难解，则右边的难解。
如果右边的 $\in P$ ，则左边的 $\in P$ 。

哈密顿路径问题HP规约到哈密顿回路问题HC

哈密顿回路问题HC规约到旅行商问题TSP

ps. 这里“否则”只要取任意大于1的数即可，保证TSP的解一定不选G中不存在的边。

最大生成树判定规约到最小生成树判定

取值 $M=\max_i{w(e_i)} + 1$ ，将所有边的权值 $w(e)$ 改成 $M - w(e)$ 。
例如下述最大边权是7，取 $M=8$ ，用 $M$ 减去所有原来的权值得到新权值。

最大生成树：有权不小于12的生成树。
最小生成树：有权不大于36的生成树。

NP-complete的规约

停机问题不是NP

下述是一个是NP-hard，但是不属于NP（从而不是NP完全）的例子。因为下述算法不存在。

从k着色问题规约到课程安排问题

NP
课程安排问题很显然是NP的，对每门课程 $C_i$ ，收集其所选方案的所有时间段，可以在多项式时间内验证时间段是否有重合。

规约
同样的边e 和同样的颜色c => 同样的时间段，所以时间段设为 $B_{e,c}$ 。
这样就可以将k着色问题的实例转化为课程安排问题的实例。

问题即是否存在这样的函数 $col: V -> \{1, \dots, k\}$ ，
使得对任意边 $(u,v) \in E$ ，都有 $col(u) \ne col(v)$ 。

直觉：如果两个顶点 u 和 v 之间有边 e，那么对于同一种颜色 c，时间段 Be,c 会同时出现在 Su,c 和 Sv,c 里。
这意味着：如果两门课选了同一种颜色 c 的方案，它们都会占用 Be,c 这个时间段 → 在同一个教室就会冲突。

从k着色实例到课程安排实例：假设是合法着色，反设。
从课程安排实例到k着色实例：假设是合法课程安排，反设。

3-SAT规约到独立集

独立集问题是 NP 完全的证明：

独立集 ∈ NP：给定集合，可在多项式时间验证是否大小为 k 且无边相连。
从 3SAT 归约到独立集问题：
给组内每对顶点添加一条边，给互反顶点之间添加一条边。

一些NP-complete的碎碎念

Circuit-SAT：给定一个电路，确定电路是否可满足（比如从电路倒推满足实例）
Cook-Levin定理：Circuit-SAT是NP-hard的。
这里是证明所有NP算法都可以规约到Circuit-SAT。方法是对每个判定算法的实例，假设它有一个验证器，这个验证器的电路可满足等价于这个判定算法的实例可判定。
从而Circuit-SAT是NP-hard的。

之后规约到3-SAT，即给定一个3-SAT，确定是否可满足（比如从3-什么玩意倒推满足实例）
形式是 (x1 || x2 || x3) && (x2 || x1 || x3) ... 这个样子的。
Circuit-SAT可以规约到3-SAT，因为可以把二元逻辑蕴含改成三元逻辑式。比如x3=x1&&x2等价于(x1&&x2&&x3) || (x1'&&x2'&&x3')。

之后3-SAT规约到Ind-Set，方法是把每个画出来，正和反的连个线，找独立集。（独立集：选点两两不相连）

之后Ind-Set和Clique（最大团）互推，因为在给边取补的图中，S就是最大团。

之后Ind-Set和Vertex-Cover（点覆盖）互推，因为V-S就是点覆盖。（点覆盖：选点覆盖所有边）

Lec17 近似算法未完成

“和最优解的值的比较”得到近似比，近似比取等的是紧实例，近似比越接近1越好。

最小顶点覆盖√，多机调度，最小集合覆盖，旅行商，0-1背包

最小顶点覆盖

最优解用到的顶点很少。
近似解是找匹配（差不多是匹配），删顶点。
通过这个近似算法，给出的解的顶点数至多是最优解的2倍。
近似比证明：假设它删了 $k$ 条边，即MVC(I)=2k个顶点；
覆盖k条互不关联的边至少需要k个顶点，OPT(I)>=k；
从而有 MVC(I)/OPT(I) <= 2k/k = 2。
紧实例：当图G由k条互不关联的边构成时，近似比=2。故MVC是2-近似算法。

多机调度问题

贪心：谁闲着给谁
贪心优化：先降序排序，谁闲着给谁

最小集合覆盖

旅行商问题

为什么不可近似：假设有近似比，我们可以搞掉HC
因为近似比以上和以下差距太大了

三角不等式
最近邻算法、最小生成树、

0-1背包

原问题无法直接贪心，因为有前后依赖。这个算法导论讲过。
分数背包才能直接贪心。
因此，0-1背包需要一个贪心近似。

十派的玩具箱