Runz's Blog

NJU 高级算法 期末复习

最坏复杂度/平均复杂度/最优性

算法的最坏复杂度/平均复杂度/最优性，概念和举例

最坏复杂度

$$ W(n) = max{t(I) | I \in D_n}$$

其中，$n$ 是规模，$t$ 是操作数量，$D_n$ 是一组输入，$I$ 是其中的一个输入。最坏复杂度就是算法处理某个输入，这个输入使算法操作数最多，所用的时间。

只需要记一下符号，用 $W$ 表示。W denotes Worst。

PPT 中举例是欧几里得算法，不过这个例子比较复杂。我建议是不如举快排最坏情况的例子。即输入为有序时，快排退化成 $O(n^2)$

平均复杂度

$$ A(n) = \sum_{I\in D_n}Pr(I)t(I)$$

$Pr$ 是某个输入出现的概率。平均复杂度是对输入集算一个操作次数的期望。

A denotes Average.

例子是一个列表中找某个 value。需要分 value 在和不在列表中两种情况讨论

最优性

如果算法 $A$ 满足：

$$ W_A(n) = F(n)$$

那么 A 就是最优的。其中 $W_A$ 是 A 的最坏复杂度。$F$ 是这个问题复杂度的下界。

这个概念有点如说的意味。

渐进复杂度

$O$, $\ohm$, $\Theta$的定义和相关函数证明

定义

不严格定义，方便记忆：

$f\in O(g)$，那 f 比 g 增长得慢；

$f\in \Theta(g)$，f 和 g 增长得一样快；

$f\in\ohm(g)$，f 比 g 增长得快。

严格定义：

$f\in O(g)$，则 $\exists c\in R^+, n_0\in N$，$\forall n >= n_0$，$f(n) <= cg(n)$。

充分条件：$f\in O(g)$ 当 $\lim_{n\to\infty}\frac{f(n)}{g(n)}=c<\infty$。注意 c 可能为 0。

另外两个定义类似。只需注意 c 的范围即可。

递归关系求解

递归关系求解：$a_n=r_1a_{n-1}+r_2a_{n-2}$ 形似斐波那契数列

递归关系特征方程

$$x^2-r_1x-r_2=0$$ 解得两根 $s_1$, $s_2$。

递推关系为：

$$a_n=us_1^n+vs_2^n$$

根据边界条件求得 u 和 v。

平滑函数与主定理

了解平滑函数性质，应⽤主定理求解⼀般式：$T(n)=bT(n/c)+f(n)$

平滑函数

平滑函数 (smooth function) 定义：

$f(n)$ 是平滑函数，当且仅当 $f(2n)\in\Theta(f(n))$

例子：$logn$, $n$, $nlogn$, $n^\alpha(\alpha>0)$ 都是平滑的。

Master Theorem 主定理

假设一个递归算法解决规模为 $n$ 的问题用时为 $T(n)$。主定理可以求出递归问题的时间复杂度。

由递归问题的性质，$T(n)$一般可以表示为递归形式：

$$T(n)=aT(n/b)+f(n)$$ 其中，a 是每次递归生成出的子问题数量，$n/b$ 是子问题规模，$f(n)$ 是处理当前问题需要消耗的代价。

设 $f(n)\in\Theta(n^d), d>=0$，可以得到这个递归算法的时间复杂度：

$$T(n)=\left{ \begin{aligned} &\Theta(n^d) & if\quad d > \log_ba \ &\Theta(n^d\log n) & if\quad d = \log_ba \ &\Theta(n^{\log_ba}) & if\quad d < \log_ba \end{aligned} \right. $$ 记忆方法，两个不等条件下可以记极端情况：

$d > \log_ba$，那就让 $d$ 趋近无穷，整个算法复杂度肯定是跟着 $\Theta(n^d)$ 即 $f(n)$，走的，所以复杂度就是 $\Theta(n^d)$。

另一个 $d < \log_ba$，那让 $f(n)$ 为 $O(1)$，这样算法的复杂度就是由递归树的节点数来决定了，因为树上每一个节点都是一个代价为 $O(1)$ 的(子)问题。而节点数为 $n^{\log_ba}$。

等于的情况就是在 $f(n)$ 复杂度的基础上乘一个 $logn$。

快排平均复杂分析

复⽤快排中平均复杂分析的⽅法来处理其它问题：$A(n)=(n-1)+\frac{2}{n}\sum_{i=1}^{n-1}A(i)$

快排每一次递归时，首先会选取一个 pivot，然后将所有元素比较一遍。比较的次数就是 n-1，即 $A(n)$ 中 n-1 的由来。

这个 pivot 等可能地分布在当前序列中的所有位置。如果 pivot 分布在第 i 个位置，那么得到了两个规模为 i 和 n - 1 - i（一个是pivot前的序列，一个是pivot后的序列）的子问题。所以这里可计算平均复杂度：

$$\sum_{i=0}^{n-1}\frac{1}{n}[A(i)+A(n-1-i)]=\frac{2}{n}\sum_{i=1}^{n-1}A(i)$$

这之中用到了 $A(1)=A(0)=0$ 的边界条件进一步化简。得到右式就是平均复杂度的第二部分。

对抗策略/对手论证 Adversary Argument

能解释对抗策略的含义、能采⽤对抗策略来分析经典问题：同时求最⼤和最⼩的问题和求取第⼆⼤元素的问题

含义

对抗策略是将算法设计者与算法分析者看作对手，同时扮演两个角色进行算法分析。算法设计者尽量多的创造更多信息，算法分析者尽量少的给予信息，拥有着随时合理改变取值的能力。

用来确定一个算法的复杂度下界。主要是基于比较的算法。

findMaxAndMin

同时求一个序列的最大值和最小值。算法能做的只有比较两个元素。

每一个元素定义如下状态：

  • W，在比较中只胜出的元素
  • L，在比较中只失败的元素
  • W/L，既有胜出又有失败的元素
  • N，没比较的元素

算法的最终状态是一个 W（最大值），一个 L（最小值），以及 n - 2 个 W/L。

初始状态是 n 个 N。

对于每一次比较，算法设计者可以得到：

  • comp(N, N) -> L, W：至少 2 个信息。这是算法分析者无法改变的。
  • comp(W, N) / comp(L, N)： 至少 1 个信息。通过让先前 W 和 L 的元素继续保持，设计者只能得到 N 元素变成 W/L 的信息
  • comp(W, L) -> W, L： 至少 0 个信息。分析者让 WL 继续保持原有赢输。
  • comp(W, W) / comp(L, L) -> W, W/L 或 L, W/L 至少 1 个信息。有一个必会得到与原来比较不同的结果，这无法改变。

对于设计者而言，首先至少得让所有 N 元素变成 W 或者 L 元素。即得到 n 个 N->W 或者 N->L。这最少需要 n / 2 次 comp(N, N) -> L, W。

然后让 n - 2 个 L 或者 W 变成 L/W。设计者利用 comp(W, W) / comp(L, L) 来让每次比较至少得到一个信息。所以至少得 n - 2 次比较。

故算法比较次数下界为 $n / 2 + n - 2 = \frac{3n}{2}-2$

第二大元素

第二大元素，就是在和最大元素比较中，失败的元素里面最大的那一个。

先研究：在寻找最大元素时，最大的元素最少进行了 $\log n$ 次比较。

考虑所有元素打积分赛。元素 $x$ 的积分为 $w(x)$。一次比较胜出后，赢家通吃输者积分。

最大元素就是 $w(x)$ 增长到 n 的元素。算法分析者可以通过下面的方式来限制所有元素的 $w$ 的最快增长速度，每一次增长不超过翻倍的速度。

  • 当 w(x) > w(y) 时，算法分析者让 x > y，即让 y 赢。这时 w(x) 增长为 w(y) < w(x)，所以增速比翻倍小
  • w(x) = w(y) 时，这增速也就将将翻倍
  • 其他情况也是无法倍增的

所以最大元素至少要 $log n$ 次增长才能结束。

和最大元素比较的输家里面找最大的一个，需要 $(\log n) - 1$ 次比较。加上一开始找最大元素的 $n - 1$ 次，总共的下界就是 $\log n + n - 2$

平摊分析 Amortized Time Analysis

含义

某些数据结构支持多种操作，其中某一些操作的代价很低，某一些很高。但是这些高代价操作偶尔发生且有一定条件。分析 n 个任意操作的时间复杂度时，不能直接将所有操作的代价视作最高的代价。而是需要平摊分析。

课程中主要介绍了 account 法。不知道中文叫什么，总之有点类似银行账户存取款。

公式为 $amortized,cost = actual,cost + accounting,cost$

Multipop Stack

一个栈。支持 push、pop、multipop。最后一个 multipop 就是将 stack 清空，代价取决于当前栈中有多少元素。

可以看到，大部分情况下 push 和 pop 操作代价很低，但是偶尔的 multipop 代价就比较高，不过这个代价仍然取决于栈中有多少元素。

均摊分析要从元素角度出发：一个元素入栈，可以预支它将来出栈的代价。无论是pop还是multipop带来的代价，都提前预支好，存在 account 中。然后将来真的 pop 了，再从 account 中取出预支的代价。

所以每个操作的 amortized cost：

  • push = 1 + 1 = 2
  • pop = 1 + (-1) = 0
  • multipop = n + (-n) = 0

加号前是 actual cost。加号后是 accounting cost，正值为预支，负值为取出。最后计算得到的结果就是 amortized cost。

做题中还需证明一下 account 始终大于等于 0。这很简单：

pop 时 stack 如果不为空，那么这些元素 (设有 n 个) push 时存了 n，pop 时只取出 1，account 不会为 0，否则 stack 为空，pop 本身就没代价。multipop 时会让 account 刚好为 0。

Delete Larger Half

一个集合，支持插入元素，以及删除当前集合中前一半大的元素。

先看 actual cost：

  • Insert: 1
  • DeleteLargerHalf: tn

插入集合就当它为 1 的代价吧。删除 LargerHalf 代价是 $O(n)$ 的，为了方便分析，给乘一个 t 来表示 $O(n)$。意义是删除 larger half 时均摊到每一个元素头上的代价是 t。

Accounting scheme(即计算 accounting cost):

  • Insert：2t
  • DeleteLargerHalf: -tn

得到均摊 cost：

  • Insert = 1 + 2t = O(1)
  • DeleteLargerHalf = tn - tn = 0

证明也很简单。假设调用 DeleteLargerHalf 时集合有 n 个元素，这里被删除的 n/2 个元素 account 里有 tn 余额，刚好抵掉。总的 accounting cost 永远不小于 0。

这个插入时预支 2t 的意义不太明确，我无法给出令人信服的解释。所以这个分析有拿着答案写过程的意味。

DFS & BFS

简述深度优先和⼴度优先算法的思想，采⽤该算法思想能解决经典的图上搜索问题：topo序、任务调度、关键路径和强联通区域问题

DFS 思想

一旦遇到可行的路径，就优先进入。实现上的特点是递归，方法的特点是回溯。在搜索树上的表现是沿着一条路径走到底，然后在回溯到上一步走其他分支。

BFS 思想

优先遍历相邻的顶点，保证搜索树上同层的顶点能够一起遍历。实现上一般使用队列来保存将要遍历的顶点。

拓扑排序

PPT 中讲的是 DFS 求拓扑序。思想是从没有 visit 的点出发，走到不能走为止。这个不能走的点（没有出边，出度为0）是拓扑序最靠后的。回溯的时候再依次地增加拓扑序的计数器。这个方法得到的拓扑序在数值上是反着的。

任务调度

依据任务的依赖关系建 DAG，拓扑序就是任务的执行顺序。

关键路径

和拓扑排序的骨架一毛一样。只是注意走到不能走的点的 est(earliest start time) = 0，然后反着回溯路径上的点就行了，每一个点做一个贪心来选取最晚的 eft。

但是要写成代码还是比较麻烦，因为涉及记录这个路径。

强连通分量

Tarjan 算法。网上一堆。

用一个 dfn 数组维护 dfs 的时间戳，再用 low 数组维护能回到的最早祖宗的时间戳。关键点在于这一段代码。已经是可以直接嗯背的程度了：

for (unsigned i = 0; i < g[v].size(); i++) {/
		ll id = g[v][i];
		//如果这个点从没访问过，则先放问它，再用它更新low[v]的值
		if (!dfn[id]) {
			tanjan(id);
			//他的儿子如果能连到更小的祖先节点，显然他也可以
			low[v] = min(low[v], low[id]); 
		}
		else {
			//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
			if (vis[id]) {
				low[v] = min(low[v], low[id]);
			}
		}
	}

贪心

贪⼼法的思想和特点，⽤贪⼼法解决经典问题并能给出证明思路：换硬币、活动安排

贪心的思想和特点

局部最优就是整体最优。

换硬币

硬币有 1，5，10，25 面额。用尽可能少的硬币凑出金额 v。

贪心策略是优先用最大的面额。需要注意的是，某些面额（如1，5，12）下，这个贪心策略是错误的。

证明：

最优解使用面额情况为 (o1, o2, o3, o4)。即 v = 1 * o1 + 5 * o2 + 10 * o3 + 25 * o4。

则有 10 * o3 < 25，否则 10 * o3 > 25，那 10 * o3 >= 30，而这 30 可以用一个 5 和一个 25 替代，得到了更优的解。

同理，5 * o2 < 10, 1 * o1 < 5。

这就说明了最优解就是贪心解，因为贪心解优先用面额大的，等价于面额小的硬币的价值不大于面额大的硬币。

活动安排

每一个活动都要使用场地，活动的时间是 [si, fi)。尽可能地安排多的活动，活动之间时间不冲突。

贪心策略是将 fi 升序排序。从前往后地无冲突地选取活动。

证明：

假设最优解安排的活动序列为 $e_{o_1}, e_{o_2}, …, e_{o_k}$。考虑逐个替换这些活动，以构造贪心解。

对于排序后的第一个活动 $e_1$，可以替换最优解的第一个活动，因为 $f_1 <= f_{o1}$，替换后对 $e_{o_2}$ 不影响。依次替换所有的活动，可以得到一个同样最优的贪心解。

DP

动态规划的思想和特点，针对经典问题能写出⼦问题的递归式，描述算法思想和伪代码：最长公共⼦序列相关问题和最优⼆叉搜索树相关问题

思想特点

子问题有最优子结构、记忆化、无后效性。

最长公共子序列

假设输入的两个序列为 $arr1$, $arr2$。算法思想是用 $c[i][j]$ 表示 $arr1[:i]$ 和 $arr[:j]$ 的最长公共子序列的长度。

边界：

$$ c[0][0] = 0 $$

递推：

$$ c[i][j] = \left{ \begin{aligned} &c[i-1][j-1]+1\quad&x[i]=y[i]\ &max{c[i][j-1], c[i-1][j]}\quad&x[i]\neq y[i] \end{aligned} \right. $$

最优二叉搜索树

思想是将原输入数组的一个区间作为子问题，记区间上问题的解为 $c[i][j]$。问题的递推是由枚举搜索树的根来实现的。

边界：

$$ c[i][i-1] = 0 $$

递推：

$$ c[i][j] = \sum_{k=i}^j p[k] + max_{r=i}^{j}{c[i][r-1] + c[r+1][j]} $$