西电-算法分析-研究生课程复习笔记

• 24年秋的应该是张老师最后一次用卷面考试，他说以后这节课的期末考试都是在OJ上刷题了
• 张老师上课还挺有意思的，上完之后能学会独立地思考算法设计问题了。整节课都在强调规模压缩这个概念，考试也是考个人对这些的理解，还挺好玩的哈哈

时间复杂度

$T(n)$ 表示算法在输入规模为 $n$ 时的实际运行时间

在实际算法设计中常用以下三种：

• $O$ 即“小于等于”，描述$T(n)$的上界。
  $1、n、2n、2n^2\in O(n^2)$
• $\Omega$ 即“大于等于”，描述$T(n)$的下界。
  $n^2、n^3、n^{10}\in \Omega (n^2)$
• $\Theta$ 表示“等于”，表示$T(n)$的上下界一致。
  $n^2,3n^2\in \Theta (n^2)$

主定理求递推式的时间复杂度
$T(n)=aT(\frac{n}{b})+f(n)$

其中 $a$ 为归约后的子问题个数，$n/b$ 为归约后子问题的规模，$f(n)$为 split 和 merge 子问题的解的工作量。

直接上例题：

1. $T(n)=9T(\frac{n}{3})+n$
   即 $a=9，b=3，f(n)=n，n^{lo{g}_{b}a}=n^2$
   因为$f(n)=n<n^2$，即case 1，$T(n)=\Theta (n^2)$

2. $T(n)=T(\frac{2n}{3})+1$
   即$a=1，b=\frac{2}{3},f(n)=1,n^{lo{g}_{b}a}=1$
   因为 $f(n)==n^{lo{g}_{b}a}$，即case 2，此时k为0，即$T(n)=\Theta (logn)$

3. $T(n)=2T(\frac{n}{4})+n^2$
   即$a=2，b=4，f(n)=n^2,n^{lo{g}_{b}a}=n^{0.5}$
   因为 $f(n)>nlo{g}_{b}a$，所以是第三种，$T(n)=\Theta (n^2)$

排序

分-治-合并。

老师说的砍规模好像就包括了分和治。

砍规模干活多，则合并时候干活少。反之同理。
二分应用于排序：对于quicksort和mergesort，快排在砍规模时先要让两边各自大于或小于pivot，较麻烦;而合并不需要显式操作，较简单。归并排序在砍规模时直接将数组分成两半，较简单;合并时要进行两个数组的排序和合并，较麻烦。

规模 n 推到规模 n-1应用于排序：选择排序、冒泡排序、插入排序，每次只减少一个问题数量，是较慢的。而这三个排序中，选择排序和冒泡排序每次少一个未排序部分的最值元素，即砍规模时多干活。而插入排序每次少一个当前游标的元素(不一定是最值)，而需要在合并时将游标元素在已排序部分插到合适的位置，即合并时多干活。

快排可能会退化，采用随机策略可以避免最坏复杂度为$O(n^2)$

特殊线性排序不考。

建堆

按照树的形态去砍规模。

砍规模干活多：比如大顶堆，先选一个最大的放在堆顶，然后递归地处理两个子树。相当于规模直接砍半，无显式合并。
$T(n)=2T(\frac{n}{2})+O(n)$，得$T(n)=\Theta (nlogn)$

砍规模干活少：从最后一个节点开始一下一下砍，直接找最后一个没用的非叶节点即可。合并是将当前子树的根节点向下调整，耗时较长。$T(n)=2T(\frac{n}{2})+logn$，得$T(n)=\Theta (n)$

Insert：把元素插入到最后一项，再向上调整。(堆排序同理)

如果要动态挑最值，可以用优先队列辅助。

Select

找数组中第k小的元素。

类似快排的partition，数组二分后看topk在哪边。

有种优化策略，将数组先分为多组(每组中奇数个元素)，再在每组找个中位数，使用中位数的中位数作为pivot做partition。避免$O(n^2)$的最坏时间复杂度。

矩阵相乘的二分方法

不考

最大子数组

找和最大的非空连续子数组。

方法1：二分，将数组分为两半，从左半部分、右半部分和跨中间这三部分的子数组中找个最大的。跨中间就是从中点往前面找个最大的后缀、往后边找个最大的前缀，相加就是跨中间的最大子数组。

方法2：DP，每次减少一个问题的规模。用一个全局变量保存历史最大子数组，并保存当前位置之前的子数组情况。如果之前的子数组之和已经为负数，则从当前位置另起一个新子数组。否则扩展之前的子数组到当前为止，即使当前元素为负数，全局变量保存的仍是之前的全局最大子数组。

DP

优化问题用到规模压缩，即DP。

• 刻画最优子结构。列递推式/状态转移方程，能用中文解释。
• 递归定义最优解的值。
• 自下而上计算。原因：需要利用子问题，而多个父问题共享某些子问题，即子问题会被重复的求解。自下而上可以避免重复求解。如果改成自上而下，则需要使用备忘录做记忆化。

有些问题不能用子问题求最优解，比如最长简单路径问题，可能两个最长简单子路径拼起来不是简单路径。

相关问题（计算题）：

1. 01背包

思路：穷举是每个物品要么放入要么不放入，$O(2^n)$。如果当前剩余容量为 k，在考虑第 i 个物品是否拿，拿不拿的两种情况，都可以利用$dp[i-1][k]$这个子问题。由于不知道 k 是多少，每次都需要扫描一遍整个容量。

2. 最大子数组

上面写了。

3. LCS最长公共子序列

思路：穷举是$O(2^{m+n})$。如果已知当前游标 $i$ 和 $j$ 前面的LCS，继而可以得到当前的LCS。即满足最优子结构。$dp$数组起到备忘录的作用。

设 $dp[i][j]$ 表示序列 $X$ 的前 $i$个字符和序列 $Y$ 的前 $j$ 个字符的 LCS 长度。

m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):for j in range(1, n + 1):if X[i - 1] == Y[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

4. 矩阵链乘

对于矩阵数组$[A1,A2,A3]$的链乘最小代价，可以通过$[A1,A2]\ast [A3]$和$[A1]\ast [A2,A3]$的代价得到，利用了$[A1,A2]$和$[A2,A3]$这两个子问题。扩展即可知道子问题就是在各个分割点分割之后的子数组，利用子问题的方式就是从子问题中选一个最值。满足最优子结构。

会重复利用较短的子数组，所以自下而上，用个dp数组做备忘录。

5. ALS装配线调度

就是给了两条装配线的进入耗时、出去耗时。然后两条装配线在功能上是相同的，有多个装配站，两条线上同一个下标的装配站是功能相同，但用时可能不同。所以有个切换操作，可以把物品从一条线搬到另一条线，试图加速。所以要求一个物品完成装配花费的最短时间。长的像最短路径，其实因为方向是固定的，所以不是图而是树，问题稍微简单一点。

dp方法见下图。

贪心

如果可以直接知道用哪个子问题也能得到最优解，不用比较各个子问题的结果，就可以贪心、即贪心$\in$DP。
相关问题如：

• 分数背包：优先选单价高的。

• 哈夫曼树：权重越高的字符，编码长度越短。权重越高，越会被后挑选，即越接近根节点。
  

• 活动选择：多个活动有起止时间，只能选互不冲突的，使活动数量最大化。DP是在当前活动处，找前面最后一个兼容本活动的活动，然后选或者不选，dp[i]是到前i个活动的最多兼容活动数。贪心策略是优先选结束时间早的，为后续活动留下更多时间。

最短路径

重点是确定通过计算次序。

之前的问题都是可以转化为一棵树，子问题向上扩展，最终得解。

而b->c、c->b都有可能，即c可以利用b之前的最短路径、b也可以利用c之前的最短路径。所以不能是一棵向上的树。所以需要确定一个计算次序，即谁是子问题。

Dijkstra

在无负权环的时候，这个计算次序是有的。他是子问题找父问题，即找一个最近的节点。如果有负权环，则有些很远节点的距离反而越来越近，计算次序就出现问题了。通过计算次序理解为什么是dp。

Bellman-ford

允许负权环，所以没有计算次序，所以迭代多轮来补偿。单源。个人感觉就是Floyd的单源形式。

SPFA就是如果有些点被更新后，才加入队列进行后续的松弛更新。

如果第V次还能松弛，说明有负权环。

Floyd

多源。$dp[i][j][k]$，已知未使用 k 时，i 到 j 的最短路径，看用 k 是否能继续缩短。

时间复杂度

floyd是$O(V^3)$。

迪杰斯特拉是每次找一个最近的点，然后基于这个中转点更新源点到中转点的邻点。所以对于邻接矩阵的实现，是V的循环里套个找邻点的V，$O(V^2)$
Bellman-ford是重复V-1次，然后松弛所有边，所以是$O(V\ast E)$

搜索

无法用规模压缩，只能蛮力穷举。

设定边界减少不必要的搜索。

限界函数：杀死更多的节点、效率。

NP问题

P可以在多项式时间内求解，NP只能在多项式问题内验证解。

NPC(理论上可解，穷举)：circuit-sat(电路可满足)、TSP(旅行商)、3-color三色(平面图染三色，使得相邻区域颜色不同)、哈密尔顿路径。

不可判定：Hilbert’s Tenth Problem(希尔伯特第十问题)、Halting Problen(停机问题)、Post Correspondence Problem(PCP)、Program Equivalence Problem(程序等价性问题)、Optimal Data Compression Problem(最优数据压缩问题)、Virus Identification Problem(病毒识别问题)、多元多项式整数根（费马大定理）、普斯特对应问题