算法分析设计课复习补充

复杂度的严谨定义

复杂度有三种表示：$O,\Omega,\Theta$

其中 $O$ 表达的是上界，定义为：

函数复杂度 $f(n)= O(g(n))$，仅当存在一个边界 $n_0$ 和常数 $c$，使得对于所有$n>n_0$，满足 $f(n)\le cg(n)$。

这个定义有极限的想法，我们可以得到 $2n^2=O(n^2)$，也有 $2n^2=O(n^3)$，上不封顶，但第二个式子没什么意义。

这里的等号是一个单向等号。

$\Omega$ 表达的是下界，定义和上文类似，大变成小：

有 $2n^2=\Omega(n)$， $\sqrt{n}=\Omega(logn)$

平时我们所说的复杂度是 $\Theta$，它是上述两者的交。

另外还有 $o$ 和 $\omega$，分别对应上述两种将大于等于改成大于、小于

严谨证明一个复杂度，需要分别证明 $O$ 和 $\Omega$

证明方法

代入法（Subtitution Method）推断

例如：对于一个递归的式子 $T(n)=4T(n/2)+n$，要求它的复杂度

运用数学归纳法，首先有 $T(1)=1$

然后猜测一个复杂度上界：$O(n^2)$，假设对于 $k<n$， $T(k)\le ck^2$ 都成立，要证明 $T(n)\le cn^2$

代入：
$$
\begin{align}
T(n)&=4T(n/2)+n \
&\le4c(n/2)^2+n \
&=cn^2+n
\end{align}
$$
证明失败…

递归树法

画出递归树，然后计算每一层的操作次数，列出一个级数式子计算。

主方法

将上述函数式写成：$T(n) = aT(n/b)+f(n)$

主方法观察两个部分哪部分起到主要作用，复杂度取决于较大者

• 若 $f(n)\lt n^{log_b{a}}$，则总复杂度为 $\Theta(n^{log_b{a}})$

  • 更准确的定义为 $f(n)=O(n^{log_b{a}-d}),d>0$，即 $f(n)$ 以某个更小的复杂度为上界，那么总体复杂度就取决于 $n^{log_b{a}}$

• 若 $f(n) =\Theta(n^{log_b{a}})$，则总复杂度为 $\Theta(n^{log_b{a}}lgn)$

  • 两边同级别，则总体复杂度乘上一个系数因子

• 若 $f(n)\gt n^{log_b{a}}$，则总复杂度为 $\Theta(f(n))$

  • 更准确的定义为 $f(n)=\Omega(n^{log_b{a}+d}),d>0$，即 $f(n)$ 以某个更大的复杂度为下界，那么总体复杂度就取决于 $f(n)$

可以知道树的高度为 $log_bn$，叶子节点共有即 $a^{log_bn}$ 个，它等于 $n^{log_ba}$（两边同时取对数可得）

其他证明略过

但这种情况无法使用主方法：$T(n)=2T(n/2)+nlogn$

$n^{log_b{a}}=n$，$f(n)=nlogn$，$f(n)$ 是渐进大于 $n$，而不是多项式大于 $n$ 的。看似是第三类，但实际上无法找到一个 $n^{1+d}$ 作为 $f(n)$ 的下界，加一点就在多项式上超过 $f(n)$ 了。而它们又显然不是同一级别，不能用第二类。

但是可以感性理解/其他方法，得到最终复杂度确实是 $nlogn$ 的

矩阵乘法

朴素复杂度为 $n^3$

考虑分治：将矩阵划为四份，每份独立相乘后再相加，$T(n)=8T(n/2)+4(n/2)^2$，复杂度仍为 $n^3$

可以采用各种结合相乘的方式，把相乘次数压到7次，虽然需要18次相加，但总复杂度能降到 $n^{2.81}$（具体乘法应该不用记）

目前最优的矩阵乘法可以做到 $n^{2.376}$

排序

快排是就地算法，它不需要临时的数组（缓存），所以产生了这么写法，本质都差不多（

随机快拍的期望复杂度证明：

设 $T(n)$ 为规模 $n$ 的随机快排的期望复杂度。

有 $T(n)=(\sum_{k=0}^{n-1}T(k)+T(n-k-1)+\Theta(n))/n$

即 $T(n)=\frac{2}{n}\sum T(k)+\Theta(n)$

此时再用数学归纳法，可以假设 $T(k)\le cklogk$

$\sum_2^{n-1} klogk$ 放缩后得到 $\le \frac{1}{2}n^2logn-\frac{1}{8}n^2$

即可得到 $T(n)\le cnlogn$

快排的效率通常是归并的两倍左右，且即便在有缓存的情况下依然有优势。

基于比较的排序最优复杂度是 $nlogn$

计数排序，桶排序等非比较排序可以做到 $O(n)$，但都不是就地算法，且需要满足一些条件。

计数排序：对所有数计数，计入 $cnt$ 数组，然后对这个 $cnt$ 数组求前缀和，此时 $cnt_i$ 表示大小为 $i$ 的数的最坏排名，再从原数组从尾到头扫一遍，每个数 $i$ 都取 $cnt_i$ 作为排名，随后将 $cnt_i$ 减一。

假设最大值为 $max$，则复杂度为 $\Theta (max+n)$

基数排序：在 $max$ 比较大时，从低位到高位依次以当前位上的值为key进行一次计数排序。

如果直接按照 $b$ 进制来分位，复杂度为 $log_{b}max(n+b)$，显然如果按十进制来分，计数排序部分只需要用10大小的数组，是有点浪费的。

我们希望左边尽可能小，而右边也控制在线性，那么取 $b=n$ 即为最优解。

若要取 $2^r$ 为一位，则 $r=log_2n$

桶排序：桶排序要求数据基本是均匀的，才能保证复杂度。

它先按最高位，将 $n$ 个数据放入 $n$ 个桶中，每个桶基本有差不多 $O(1)$ 个数据，故对桶内排序基本也是 $O(1)$ 的，然后再将各个桶连接起来。

哈希

哈希函数的选取，希望能将键均匀的映射到所有地址上。

且不希望取值的规律性导致映射规律性

故一般取模值为质数，使得数和模数互质。（取模策略）

对于计算机中用 $w$ 位保存的数，还可以乘以一个奇数，让它超过 $2^w$ 自然溢出，取最后数 $w$ 位中的 $r$ 位作为哈希值。这相当于乘奇数，对 $2^w$ 取模，乘数与模数互质，它能遍历到所有可能的结果，且运算会比取模更快。

解决冲突：

• 链表法

  • 装载因子（装载的比例 $n/m$）为 $a$ 时，查找失败的期望次数为 $1+a$
  • 查找成功的期望有相同的渐进边界，但严格边界比较难算。

• 开放地址法

  • 连续编号，容易聚集，导致搜索效率下降
  • 双哈希，好
  • 装载因子为 $a$ 时，开放地址法查找的期望次数是 $1/(1-a)$

全域哈希

如果被别人知道了我们使用的哈希函数，对方就可以构造一组全部冲突的数据，很容易卡。

全域哈希即在程序运行之前，随机选取哈希函数，使得对于任何构造的数据，冲突的概率仍然是 $1/m$（假设哈希表有 $m$ 个槽）

随机选取的哈希函数需要满足这样的条件：假设哈希函数库为 $H$，对于任意不相同的 $x，y$，$H$ 当中恰好存在 $H/m$ 个函数使得它们冲突。

构造者不知道我们会随机到那一个函数，那么对于任意的数据，冲突的概率即 $(H/m)/H=1/m$

构造方法：

将键值 $k$ 转化为 $m$ 进制数，假设转化后一共有 $r+1$ 位，表示为 $k=<k_0,k_1,…k_r>$

对每一位取随机值 $a_i\in[0,m)$，哈希值 $h(k)=\sum a_i\times k_i$，对 $a$ 的不同取值决定了不同的哈希函数，共有 $m^{r+1}$ 种。

证明：

暂时跳过

完全哈希

没看懂 先跳了

二叉搜索树

<<<<<<< HEAD
随机构建：类似快速排序的方式，对整个序列进行partition到左右两部分。

随机构建的期望树高：是 $logn$ 的，比较直观证明略

红黑树：

=======
随机构建：类似快拍方式，随机选取一个点作为中间，然后隔断到两边向下构建，复杂度同快排

随机构建的期望树高为 $log_2n$，证明太麻烦跳了（这个感觉完全可以感性理解…）

红黑树

性质：

• 根节点是黑的，叶子节点（NIL节点）是黑色
• 没有连续的红节点
• 根节点到任意叶子节点（NIL）节点的路径上黑色节点数相同

为什么要有NIL节点？它和插入有关，详见下文。

红黑树本质是2-3-4树（一种逻辑结构）的一种实现，有一个红儿子的黑节点为实际的3节点，有两个红儿子即为4节点。

可以把红节点都向上压一层，和它的黑父节点放在一排，就能看出红黑树其实是一个2-3-4树，黑色节点数平衡其实是在2-3-4树上的节点平衡。当然满足了黑色节点平衡，总节点不平衡也不会夸张到哪里去了。

$n$ 个节点的红黑树树高有 $h\le2log_2(n+1)$，如果压成2-3-4树，则 $h’\ge h/2$

插入：

首先将新数据视为红色节点按普通二叉搜索树方式插入，这样不会违反性质3。

但倘若我们在一个红色节点的一边插入，另一边已经有个黑色节点，那么插入后还是会违反性质3的。

所以有NIL节点的存在，它要求红色点哪怕只有一个儿子，另一边算上NIL，也要纳入性质3的考量。事实上，这样要求后红节点已经不可能出现只有一个儿子的情况了，插入便能保存性质。

插入后具体的旋转和改色不再赘述。

堆

堆（普通二叉堆）的插入平均复杂度是 $O(1)$ 的（基于概率的期望是 $O(1)$，最坏还是可以卡到 $log$），取数是 $log$，构建和合并都是 $O(n)$，手写堆维护一下下标即可任意修改。

二项队列：做到了 $O(logn)$ 的堆合并，平均插入也是 $O(1)$，算法很妙，此处不赘述

斐波那契堆：实现比较复杂，常数也大，但是有 $O(1)$ 的插入

图

握手定理：无向图度数和等于边数x2

最小生成树中也包含最优子结构（任取一部分点，子图的MST包含在总图的MST中）

Prime：

朴素复杂度 $V^2$

使用手写二叉堆，一个节点最多修改 $Ei$ 次（最短距离最多被更新 $E_i$ 次），故复杂度为 $ElogV$

若使用优先队列，无法直接修改，必须都插入，则队中最多 $O(E)$ 个元素，复杂度 $ElogE$

斐波那契堆下为 $E+VlogV$

Kruskal：$ElogE+ (V+E) \alpha(V)$，$\alpha$ 为并查集复杂度

最短路中也包含最优子结构（最短路径的一部分也是最短路径）

Dijkstra：复杂度和各种优化复杂度都和Prime同理

Bellman-Ford：复杂度 $O(VE)$，扩展 $n-1$ 轮后若还有可松弛的边，则有负环。

全源最短路：

非最优的dp做法：

将松弛理解为矩阵相乘，相乘的定义改为两两相加取 $min$，相乘的两个矩阵分别表示当前 $i$ 到 $j$ 的最短距离，和 $i$ 连 $j$ 的边长，将二者相乘一次即做一次扩展，乘 $n-1$ 次即可得到全源最短路。

复杂度 $n^4$，运用矩阵快速幂（在这个相乘意义下仍有结合律）可以有 $n^3logn$

floyd：也是动态规划，$f_{k,i,j}$ 表示仅经过前 $k$ 个节点，从 $i$ 到达 $j$ 的最短路径，先枚举松弛中点，复杂度 $n^3$

Johnson：见acm笔记

Floyd的多源最短路 $O(n^3)$，很容易想到，如果进行 $n$ 次Dijkstra也不过 $O(nmlogm)$，但是不能处理负权边

有没有什么办法修改一下边权强行跑dij呢？

• 如果我们给每个节点随便加一个点权 $h_i$，把连接 $u→v$ 的边权改为 $w+h_u-h_v$
• 那么原图中任意一条路径 $s→x_1→x_2→..x_n→t$ 长度为 $w_{s,x1}+w_{x1,x2}+..w_{x_n,t}$
• 而在新图中，这条路的长度为 $w_{s,x1}+w_{x1,x2}+..w_{x_n,t}+h_s-h_t$
• 可以发现 $s,t$ 间的任一一条路径长度都仅仅只是加上了始末节点的 $h$ 值差，与路径无关（有没有想到势能）
• 所以在这个新图中找到的最短路也是老图中的最短路，值减去 $h_s-h_t$ 即可

上述我们说明了可以给节点加上任意权值，修改边权后不影响最短路

现在还需要修改后的边权都不为负，这样我们才能跑Dijkstra

也就是要求任意 $w+h_u-h_v \ge 0$，即 $h_v \le h_u +w$ （最短路！）

所以，$h$ 数组是任意源点出发的最短路即可

Johnson多源最短路的流程也就很明确了：

• 随便找个点，跑一遍单源最短路，得到最短路数组 $h$
• 依据 $h$，修改所有边权
• 再对每个节点跑一遍Dijkstra，得到多源最短路

为了方便判负环，第一步可以建一个0号节点，和所有点连长度为0的边，然后Bellman-Ford跑第一遍最短路顺便判负环。

预处理复杂度 $O(nm)$，，总复杂度 $O(nmlogm)$，在费用流中也有应用

网络流

割的概念：割是两个点集 $(A,B)$，其中源点在 $A$，汇点在 $B$

割的容量定义为：从 $A$ 到 $B$ 的所有边容量之和，最小割即选取 $(A,B)$ 使得割的容量最小。

重点理解：割是点集而非边集，虽然它对应了一个边集

在任何一个流 $f$ 下选取任何一个割 $(A,B)$，流的流量都等于割中 $A\to B$ 的流量减去 $B\to A$ 的流量，且$val(f)\le cap(A,B)$，因为要减去 $B\to A$ 的流量。

最大流等于最小割，同时若 $val(f)=cap(A,B)$，则它们为最大流和最小割。

Ford-Fulkerson算法：即不断寻找增广路，扩展，直到没有增广路为止。

具体找增广路的方式有EK，Dinic等算法

贪心

概念：贪心选择（局部最优选择达到全局最优）

两个要素：最优子结构（和dp一样），贪心选择性质（需要作出选择时，只选看起来最优的，并期望局部最优推出全局最优）

备忘录方法（自顶向下，即记搜），自底向上（一般dp，用的最多）

活动选择问题：

即给出若干个活动的开始结束时间，只有一个场地可使用，求最多能进行几个活动。

首先按照结束时间排序

dp搞法：$f_{i,j}$ 表示在 $i$ 活动结束后，$j$ 活动开始前最多进行多少个活动

$f_{i,j}\leftarrow f_{i,k}+f_{k,j}+1$

贪心：选择第一个结束的活动，再不断往后选最早结束不冲突的活动

步骤：

• 将优化问题转化为一个我们做出选择，只剩下一个子问题要解决的问题。

• 证明总是有一个最优解做出贪婪的选择，这样贪婪的选择总是安全的。

• 证明了子问题的贪婪选择和最优解能导出问题的最佳解决方案。

• 做出贪婪的选择，自上而下解决问题。

• 可能需要对输入进行预处理

回溯法

问题的解空间理论：

问题的解空间即我们在穷举时的搜索空间，解空间需要包含所有正确的解，好的解空间应该尽可能减少错误解和重复解

问题的解的表示方式和解释隐含了解空间及其大小

解空间一般用解空间树的方式组织，根节点到叶子结点的路径构成了一个可能解。

剪枝即在没有完全得出当前解时，预先判断当前的解空间子树中是否包含最优解，若必不包含则可以直接回溯，不必再搜。

剪枝包括通过约束条件减去得不到正确解的子树，和通过目标函数减去得不到最优解的子树

解向量：即解的表示方法

一些经典的NPC问题：

• 旅行商问题（TSP）

• 装箱问题（背包问题）

  • 此处有个重大误区，即标准时间复杂度的定义：
  • 将数据规模严谨定义为保存数据需要的位数，如 32bit 的 $n$ 个元素的数组，数据规模为 $32n$
  • 在这种定义下，大多传统算法不受影响，如冒泡排序可能变成 $32^2n^2$，不影响复杂度
  • 但在数论场合，一个整数 $x$ 的实际大小是随着其二进制位数指数增长的，例如跑一半的质数判断，在传统复杂度下为 $O(n)$，标准复杂度下为 $O(2^n)$
  • 这种在传统复杂度为多项式但在标准复杂度下非多项式的称为伪多项式时间
  • 背包问题 $O(nd)$，$d$ 为容量，是一个数，在标准复杂度意义下它已经是指数增长的了，故背包问题为NPC

• 作业调度问题

• 最大团问题

等等等等

2c9fa93e0b0d283c9d0f6b386b00eff25bcfb10e

重排原理：优先选取分支数少的特征来走，这样剪枝能剪得多一些

效率分析：要考虑计算约束条件和目标函数的代价，折中选取剪枝。