算法复习速通
软小宣（大作业的玩物版）
前言：
期末考试占50%，平时作业40%，课堂表现10%。
如果作业认真写并且课堂每节课都去的话。拿A-需要考81分，B+需要考72分。
认真考试！
课堂大纲：
- 算法基础
会考两道解递归式的题其中重点的是解递归式的解法- 分治思想
- 分类与排序
就是几类排序算法，感觉会结合选择题考注意掌握一下每个算法的大致流程- 动态规划
会考一道算法设计题重点是学会基本流程，以及递归式的求法- 贪心算法
会考一道算法设计题和上述相同要求- 摊还分析
没提到明确归宿感觉会考算法复杂度分析- 并查集
没提到明确归宿- 串匹配
没有提到明确归宿重点看看串匹配逻辑算法设计与复杂度- NPC问题
会考一道证明题学会规约的方法- 近似算法
- 多线程算法
会考一道算法设计题考试内容（2024）：解递归式、两道选择题（单选、很杂、正确错误与否）、一道证明题（证明NPC）、三道算法设计题、以及分析算法复杂度的题
猜测2024是2+2+1+3+2的模式
参考2023的考试内容是：10道题：两道选填大题，NPC会考证明（归约），四道复杂度计算题+分析题，三道算法设计题（dp，贪心，多线程）
[toc]
1. 算法基础
相关知识点是算法复杂度介绍、一些常用的算法分析数学函数、==用递归法解算法复杂度==、主方法（解递归式的辅助方法，也需要掌握）
这里会考==解递归式==
- 算法复杂度的表现形式：
渐进上界：\(f(n)=O(g(n))\)、\(f\le g\)
渐进下界：\(f(n)=\Omega(g(n))\)、\(f\ge g\)
严格上界：\(f(n)=o(g(n))\)、\(f<g\)
严格下界：\(f(n)=\omega (g(n))\)、\(f>g\)
渐进紧密界：\(f(n)=\Theta(g(n))\)、\(f=g\)
-
常见算法分析的数学函数：
-
\(n!=o(n^n)\) \(n!=\omega (2^n)\) \(\lg(n!)=\Theta(n\lg n)\)
-
迭代对数函数 \(\lg^* n = \min \{ i \geq 0 : \lg^{(i)} n \leq 1 \}\)
n=2 1次、n=4 2次、n=16 3次、n=65536 4次 -
==代换法==计算算法复杂度
substitution
步骤：猜测解的形式、用数学归纳法进行证明。\(Guess\rightarrow Verify\)
Tip：需要不断放大和缩小猜测，使得其被满足且足够紧致；一般用来证明小于等于
例题1（代换法猜测）
\(T(n) = 9T\left(\left\lfloor \frac{n}{3} \right\rfloor\right) + n\)
观察：\(T(1)=\Theta(1)\)；
猜测：\(T(k)\le ck^3\)；论证：\(T(n)\le cn^3/3+n\le cn^3\)；猜测成立；但是不紧致
猜测：\(T(k)\le ck^2\)；论证：\(T(n)\le cn^2+n\)；猜测不成立
猜测：\(T(k)\le c_1k^2-c_2k\)；猜测成立
- ==递归树法==计算算法复杂度
递归树模型化了递归算法执行的成本。递归树的每个节点表示一个单独子问题的成本。递归树适用于生成一个良好的猜测。
例题2（递归树法产生良好猜测）
\(T(n) = T\left(\left\lfloor \frac{n}{4} \right\rfloor\right) + T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + \Theta(n^2)\)
分析：tree 0 cn^2^ tree 1 5/16cn^2^ tree 2 (5/16)^2^cn^2^
\(T(n)=cn^2(1+\frac{5}{16}+(\frac{5}{16})^2+(\frac{5}{16})^3+\dots)=Θ(n^2)\)
- ==主方法==计算算法复杂度
形如\(T(n) = aT( \frac {n}{b} )+ f(n)\)的递归式
重点是\(f(n)\)与\(n^{\log_ba}\)的关系
+ 如果函数$f(n)$可以表示为$O(n^{\log_b a - \epsilon})$，其中$\epsilon>0$是一个常数，那么递归式的解$T(n)$将是$\Theta(n^{\log_b a})$
+ 如果函数$f(n)$可以表示为$\Theta(n^{\log_b a})$，那么递归式的解$T(n)$将是$\Theta(n^{\log_b a}lgn)$
+ 如果函数$f(n)$可以表示为$\Omega(n^{\log_b a + \epsilon})$，其中$\epsilon>0$是一个常数，并且存在一个常数$c<1$以及对于足够大的n，满足$af(\frac{n}{b})\leq cf(n)$，那么递归式的解$T(n)$将是$\Theta(f(n))$【注意第三种情况的特殊要求】
例题3（用主方法解递归式）
1. \(T(n)=9T(n/3)+n\)
分析：\(a=9,b=3,f(n)=n,n^{log_b a}=n^{log_39}=n^2\)
\(f(n)=\)\(O(n^{\log_b a - \epsilon})\)，其中\(\epsilon=1\)，满足第一种情况，因此解为：\(T(n)=\Theta(n^2)\)
2. \(T(n)=T(2n/3)+1\)
分析：\(a=1,b=\frac{3}{2},f(n)=1,n^{log_b a}=n^{log_{\frac{3}{2}}1}=n^0=1\)
\(f(n)=\Theta(n^{\log_b a })\)满足第二种情况，因此解为：\(T(n)=\Theta(lgn)\)
3. \(T(n)=3T(n/4)+n\lg n\)
分析：\(a=3,b=4,f(n)=n\lg n,n^{\log_ba}=n^{log_43}\)
且存在c，\(\frac{3}{4}n(\lg n-2)\le c n\lg n\)
满足第三种情况，因此解为：\(T(n)=\Theta(n\lg n)\)
2. 分治思想
这里感觉是大致介绍分治思想，再讲几个例子。
考点应该不密集
- 分治思想的步骤
\(Divide：D(n)\rightarrow Conquer:aT(n/b)\rightarrow Combine:C(n)\)
总复杂度：\(T(n)=aT(n/b)+D(n)+C(n)\)
插嘴：感觉回到了主方法那边
- 案例集：
- MergeSort：\(T(n)=2T(n/2)+\Theta(n)+\Theta(1)\)
- 斐波那契数列：\(\begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) \\ F(0) \end{bmatrix}\) \(T(n)=T(n/2)+\Theta(1)=\Theta(\lg n)\)
- 大数乘法：\(x=a⋅10^k+b~~~y=c⋅10^k+d\) \(x⋅y=ac⋅10^{2k}+(ad+bc)⋅10^k+bd\) \(T(n)=3T(n/2)+\Theta(n)=\Theta(n^{\lg3})\)
- 矩阵乘法：
- 暴力\(T(n)=\Theta(n^3)\)
- 分治1：将其分成四个对半矩阵进行相乘。\(T(n)=8T(n/2)+\Theta(n^2)=\Theta(n^3)\)
- 分治2：斯特拉森(Strassen)算法，只用算7次乘积，再构造出最新的子块。\(T(n)=8T(n/2)+\Theta(n^2)=\Theta(n^{2.81})\)
- 最近点对：\(T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)\)
3. 分类与排序
| 排序算法 | 基本逻辑 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 | 关键思想 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | 重复遍历列表，比较相邻元素并交换错序对 | \(\(O(n^2)\)\) | \(\(O(n^2)\)\) | \(\(O(n)\)\) | \(\(O(1)\)\) | 稳定 | 通过相邻比较和交换来排序 |
| 选择排序 | 逐轮选择最小元素置于未排序序列的开头 | \(\(O(n^2)\)\) | \(\(O(n^2)\)\) | \(\(O(n^2)\)\) | \(\(O(1)\)\) | 不稳定 | 一轮轮选择最小值，然后放到已排序序列的末尾 |
| 插入排序 | 构建有序序列，为未排序数据在已排序序列中找到合适位置并插入 | \(\(O(n^2)\)\) | \(\(O(n^2)\)\) | \(\(O(n)\)\) | \(\(O(1)\)\) | 稳定 | 类似整理手中的扑克牌，逐个将元素插入到适当位置 |
| 归并排序 | 分治法，将列表持续分割成半，然后归并时排序 | \(\(O(n \log n)\)\) | \(\(O(n \log n)\)\) | \(\(O(n \log n)\)\) | \(\(O(n)\)\) | 稳定 | 分而治之，先递归分割列表，然后合并时排序 |
| 快速排序 | 选择一个“基准”元素，通过分区操作，使得小于基准的放左边，大的放右边 | \(\(O(n \log n)\)\) | \(\(O(n^2)\)\) | \(\(O(n \log n)\)\) | \(\(O(\log n)\)\) | 一般不稳定 | 分治法，但通过基准和分区来实现，非常适合大数据集 |
| 希尔排序 | 使用增量序列来分组，对每组使用插入排序，最后一次全体构成一组 | 通常 \(\(O(n \log n)\)\) | \(\(O(n^{1.5})\)\) | \(\(O(n)\)\) | \(\(O(1)\)\) | 不稳定 | 插入排序的改进版，通过减少逆序对数量来提高效率 |
| 堆排序 | 利用堆这种数据结构设计的排序算法 HEAPSORT：从上往下，不断将根节点A[1]的最大元素和A[n]互换，再去掉节点A[n] O(n lg n) |
\(\(O(n \log n)\)\) | \(\(O(n \log n)\)\) | \(\(O(n \log n)\)\) | \(\(O(1)\)\) | 不稳定 | 利用大根堆或小根堆的性质，实现排序 |
| 计数排序 | 计算每个元素的出现次数，根据元素的关键字顺序来构造输出的有序序列 | \(\(O(n+k)\)\) | \(\(O(n+k)\)\) | \(\(O(n+k)\)\) | \(\(O(k)\)\) | 稳定 | 非比较排序，适用于有限范围内的整数排序 |
| 桶排序 | 将数据分到有限数量的桶里，每个桶再分别排序 | \(\(O(n+k)\)\) | \(\(O(n^2)\)\) | \(\(O(n)\)\) | \(\(O(n+k)\)\) | 稳定 | 利用函数映射将数据分布到各个桶，每个桶内部再排序 |
| 基数排序 | 通过键值的部分信息，将数据分配到各个桶中，逐级排序 | \(\(O(n \cdot k)\)\) | \(\(O(n \cdot k)\)\) | \(\(O(n \cdot k)\)\) | \(\(O(n+k)\)\) | 稳定 | 按位数切割数字，分别进行排序，从最不重要的位开始到最重要的位 |
4. DP动态规划
-
如果某一问题有很多重叠子问题，使用动态规划是最有效的。
-
DP的三大条件：
-
最优子结构：原问题最优解涉及多少子问题；确定最优解时使用哪些子问题，考察的选择空间
-
无后效性：已经求解的子问题，不会受到后续决策的影响
-
子问题重叠：如果大量重叠子问题，可以用空间存储，避免重复，提升效率
-
最优子结构四步：
拆分问题：首先，将问题分解成一个或多个子问题。
假设最优选择：假设你已经知道了哪个选择会导致最优解。
分析子问题：在给定这个选择的情况下，尽可能详细地描述由此产生的子问题的空间。
证明子问题的最优性：使用“剪切-粘贴”技术来证明选择的子问题确实是最优的。
-
DP例子分析
-
rod cutting 切钢筋问题
dp：\(r_n=\max (p_n,r_1+r_{n-1},r_2+r_{n-2},\cdots,r_{n-1}+r_1)\)
递推：\(2^n\)；DP：\(n^2\)
-
Matrix-charin 矩阵链乘法问题
其目标是找到一种乘法顺序，使得计算一系列矩阵乘积所需的标量乘法次数最小。
Example：\(\left(A_1\left(A_2\left(A_3 A_4\right)\right)\right),\left(A_1\left(\left(A_2 A_3\right) A_4\right)\right),\left(\left(A_1 A_2\right)\left(A_3 A_4\right)\right), \left(\left(A_1\left(A_2 A_3\right)\right) A_4\right),\left(\left(\left(A_1 A_2\right) A_3\right) A_4\right)\)
\(m[i][j]=\min _{i \leq k<j}\left(m[i][k]+m[k+1][j]+p_{i-1} \times p_k \times p_j\right)\)
\(n^3\)
-
longest common subsequence 最长公共子序列
\(c[i, j]= \begin{cases}0 & \text { if } i=0 \text { or } j=0, \\ c[i-1, j-1]+1 & \text { if } i, j>0 \text { and } x_i=y_j, \\ \max (c[i, j-1], c[i-1, j]) & \text { if } i, j>0 \text { and } x_i \neq y_j .\end{cases}\)
（设 \(d p[i][j]\) 表示序列 \(X[1 . . i]\) 和 \(Y[1 . . j]\) 的最长公共子序列的长度）
\(m\times n\)
连续的情况：\(d p[i][j]= \begin{cases}0 & \text { if } i=0 \text { or } j=0 \\ d p[i-1][j-1]+1 & \text { if } x_i=y_j \\ 0 & \text { if } x_i \neq y_j\end{cases}\)
（定义 \(d p[i][j]\) 为以 \(x_i\) 和 \(y_j\) 结尾的最长公共子串的长度）
-
Optimal binary search tree 查字典问题
\(e[i, j]= \begin{cases}q_{i-1} & \text { if } j=i-1, \\ \min _{i \leq r \leq j}\{e[i, r-1] +e[r+1, j]+w(i, j)\} & \text { if } i \leq j .\end{cases}\)
e是子树花销、w是点单次消费之和。
\(n^3\)
5. 贪心算法
关键是设计贪心算法与贪心解答时给出最优性证明
-
基本特点
-
局部最优选择：在每一步选择中，贪心算法都会从剩余的选择中选取当前看起来最优的选择，而不考虑这一选择的长远影响。这一点与动态规划不同，后者会评估每一步选择的后续结果。
- 无回溯：一旦作出了选择，就不会再改变。这意味着贪心算法通常更简单且更快，但也更容易错过全局最优解。
-
简单高效：贪心算法通常比其他算法（如动态规划或回溯算法）更简单，编码更直观，且在适合的问题上可以提供非常高的效率。
-
适用条件
-
最优子结构：一个问题的最优解包含其子问题的最优解。
-
贪心选择性质：通过局部最优选择，可以确保最终的解是全局最优的。
-
证明最优解的正确性
-
反证法：
`（不贪心不行）不贪心得到的解法不会比贪心的更好交换方案中任意两个/相邻元素后, 答案不会更好。 -
归纳法：先算得出边界情况（例如 \(n=1\) ）的最优解 \(F_ 1\), 然后再证明：对于每个 \(n\)， \(F_{n+1}\) 都可以由 \(F_{n}\) 推导出结果。
-
交换论证法：
（从不贪心的能保持最优性的前提下交换得到贪心解）从非贪心策略得到的最优解出发, 在保证最优性不变的前提下, 从一个最优解进行逐步替换, 从而得到贪心策略的解。 -
贪心算法案例分析：
-
Huffman codes 哈夫曼编码问题 $$ \begin{equation} \begin{aligned} &\operatorname{HUFFMAN}(C)\ &1\quad n=|C|\ &2 \quad Q=C\ &3 \quad\text { for } i=1 \text { to } n-1\ &4\quad\quad\text { allocate a new node } z\ &5\quad\quad z . l e f t=x=\text { EXTRACT-MIN }(Q)\ &6\quad\quad \text { z.right }=y=\text { EXTRACT-MIN }(Q)\ &7\quad\quad z . \text { freq }=x \text {.freq }+y \text {.freq }\ &8\quad\quad \text { INSERT }(Q, z)\ &9\quad\text { return EXTRACT-MIN }(Q) \end{aligned} \end{equation} $$
-
拟阵 Matroids
M=(S,I)；S是优先级、I是子集的一个非空族，这些子集称为S的独立子集
- 最大独立子集
- 遗传性
- 交换性
-
贪心选择性质：
-
最优子结构性质：
-
任务调度问题 A task-scheduling problem
策略：首先考虑所有能够按时完成的任务，并根据它们的截止日期进行排序和调度。这种方法不仅确保了所有可以按时完成的任务都得到了适当的处理，还优化了任务完成的顺序，使得尽可能多的任务能够按时完成。
任务调度流程：
- 找出一组应在最优调度中提前完成的任务集合 A。
- 一旦确定了集合 A，我们可以通过按截止日期的单调递增顺序列出 A 的元素来创建实际的调度。
- 以任意顺序列出延迟的任务（即 S − A），生成最优调度的规范排序。
| \(a_i\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| \(d_i\) | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
| \(w_i\) | 70 | 60 | 50 | 40 | 30 | 20 | 10 |
如上表，最终解为：\(\left\langle a_2, a_4, a_1, a_3, a_7, a_5, a_6\right\rangle\)，最终花销是\(w_5+w_6=50\)
Running time：\(O(n^2)\)
6. 摊还分析与堆
- 动态表扩充算法
TABLE-INSERT}(T,x
if T.size == 0
allocate T.table with 1 slot
T.size = 1
if T.num == T.size
allocate new-table with 2 - T.size slots
insert all items in T.table into new-table
free T.table
T.table = new-table
T.size = 2 . T.size
insert x into T.table
T.num = T.num + 1
这种算法实际最坏的复杂度是\(O(n^2)\)
-
摊还分析是一种分析操作序列的策略，用以展示每个操作的平均成本很小，尽管序列中的某个单一操作可能非常昂贵。
-
the aggregate method：聚合分析，计算整个操作序列的总成本，然后将其平均到每个操作上。这种方法适用于所有操作都会被执行且次序固定的情况。
- ：核算法，为每个操作分配一个假设的“成本”，这些成本既覆盖了操作本身的实际成本，也可能包含一部分为将来的操作预存的成本。这样可以确保每个操作的分配成本始终覆盖其实际成本，同时为将来可能出现的高成本操作积累足够的预算。
-
the potential method：势函数法，类似于物理中的势能概念，系统的“势能”与数据结构的某种状态相关联。操作可能会改变系统的势能，增加（存储能量）或减少（释放能量），而这种变化被用来支付操作的成本或者补偿低成本操作。
-
聚合分析：
定义操作序列： 首先，确定需要分析的操作序列，这些操作通常是在同一个数据结构上进行的。
计算总成本： 计算执行整个操作序列的总成本。这包括每个操作的单独成本，无论它们是高是低。
平均成本： 将总成本除以操作的总数，得到每个操作的平均成本。
例如：加法翻转运算，由于往高位走是lg级别递减，因此最坏情况也是O（n），摊还到每一步是O（1）
- 核算法：
设定摊销成本： 对每个操作设定一个摊销成本，这个成本不一定与操作的实际执行成本相同。这个设定的成本被称为“摊销成本”。
信用和债务： 当某个操作的摊销成本高于其实际成本时，多出来的成本被视为“信用”存入一个虚拟的“银行”。相反，如果某个操作的摊销成本低于其实际成本，那么它需要从“银行”中借用之前存入的“信用”来支付差额。
保持总体平衡： 整个操作序列结束时，银行中的信用应足以支付所有欠下的债务，这样总的摊销成本就能覆盖所有操作的总实际成本。
例如：动态数组的扩容：将每次插入操作的摊销成本设为一个较大的常数（例如3倍单个插入的平均成本），这个额外的成本在大多数时间里被积累为信用。
当发生扩容时，使用积累的信用来支付扩容的实际高成本。
学会填分析表：\(c_i\)花销、\(\hat{c}_i\)摊销成本、\(Credit_i\)信用
-
势函数法：
-
定义势能函数 \(\Phi(D)\) ：根据数据结构和操作特点定义一个适当的势能函数。
-
初始化势能: 给出初始数据结构 \(D_0\) 的势能 \(\Phi\left(D_0\right)\) 。
-
计算每次操作的㧐销成本: 对于第 \(i\) 次操作，㧐销成本 \(\hat{c}_i\) 计算如下:
\(\hat{c}_i=c_i+\Phi\left(D_i\right)-\Phi\left(D_{i-1}\right)\)
其中 \(c_i\) 是操作的实际成本， \(\Phi\left(D_i\right)-\Phi\left(D_{i-1}\right)\) 是势能的变化。
例如在动态表扩容里面\(\Phi(D)=2 \times \text { num }- \text { size }\)
如此计算每次也是2，最后能得到O(n)的总复杂度
7. 并查集（Data Structures for Disjoint Sets)
- 并查集的三个操作：
- MAKE-SET(x): 创建一个新的集合，其唯一成员（因此也是代表）是 x
- UNION(x, y): 合并包含 x 和 y 的两个不相交的动态集合
- FIND-SET(x): 返回包含 x 的唯一集合的代表的指针
//初始化
int fa[MAXN];
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
fa[i] = i;
}
//查询
int find(int x)
{
if(fa[x] == x)
return x;
else
return find(fa[x]);
}
//路径压缩
int find(int x)
{
if(x == fa[x])
return x;
else{
fa[x] = find(fa[x]);//父节点设置为根节点
return fa[x]; // 返回父节点
}
}
//一般的合并
inline void merge(int i, int j)
{
fa[find(i)] = find(j);
}
- 将按秩合并和路径压缩结合使用，可以使最坏情况下的运行时间达到O(mα(n))，其中α(n)是一个增长非常慢的函数。在任何可以想象到的使用不相交集合数据结构的应用中，α(n) ≤ 4，因此，其运行时间实际上与m成线性关系。
按秩合并（Union by Rank）和路径压缩（Path Compression）是并查集（Disjoint-set data structure）中两个非常重要的优化技术。这两种方法的结合可以显著提高数据结构操作的效率，尤其是在处理大量动态集合合并和查找操作时。下面，我们将详细探讨这两种技术是如何实现的，以及它们是如何共同作用来达到最坏情况下的运行时间为\(O(m \alpha(n))\) 的。
按秩合并 (Union by Rank)
在并查集数据结构中，每个元素指向一个父元素，所有的元素共同形成一个森林，每棵树代表一个集合。按秩合并的基本思想是在执行合并（Union）操作时，总是将较小的树的根指向较大的树的根。这里的“秩”通常代表树的高度或者深度（尽管也可以是其他能代表树大小的度量），通过这种方法，可以避免形成高度过高的树，从而在执行查找操作时减少路径长度。
路径压缩 (Path Compression)
路径压缩是在执行查找操作（Find）时使用的技术。当查找元素的集合代表时，路径压缩技术会将查找路径上的每个节点直接连接到树的根节点。这样，下一次执行查找操作时，路径将大大缩短，从而加快查找速度。
- The amortized cost of each MAKE-SET operation is O(1)
The amortized cost of each LINK operation isO(α(n)).
The amortized cost of each FIND-SET operation is O(α(n)).
A sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank and path compression in O(mα(n)) time.
8. 串匹配
- 问题描述：
字符串匹配问题是要在文本 \(T[1 \ldots n]\) 中找到字符串 \(P[1 \ldots m]\) 的所有出现。我们进一步假设 \(P\) 和 \(T\) 的元素是从有限字母表 \(\Sigma\) 中提取的字符。例如，我们可能有 \(\Sigma=\{0,1\}\) 或 \(\Sigma=\{a, b, \ldots, z\}\) 。如果 \(0 \leq s \leq n-m\) 且 \(T[s+1 \ldots s+m]=P[1 \ldots m]\) ，我们说字符串 \(P\) 在文本 \(T\) 中以偏移 \(s\) 出现。
- 算法列举及复杂度分析： $$ \begin{aligned}
&\begin{array}{lcc} \text { Algorithm } & \text {预处理 Preprocessing } & \text { 匹配时间 Matching time } \ \hline \text { Naive } & 0 & O((n-m+1) m) \ \text { Rabin-Karp } & \Theta(m) & O((n-m+1) m) \ \text { Finite automaton } & O\left(m\left|\sum\right|\right) & \Theta(n) \ \text { Knuth-Morris-Pratt } & \Theta(m) & \Theta(n) \ \text { Boyer-Moore } & \Theta\left(m+\left|\sum\right|\right) & \Omega(n / m), O(m n), O(n) \ \text { Shift-Or } & \Theta\left(m+\left|\sum\right|\right) & \Theta(n) \ \text { Reverse Factor } & O(m) & O(m n), O(n(\log m) / m) \ \hline \end{array} \end{aligned} $$
- 前缀后缀：
\(a b \sqsubset a b c c a, c c a \sqsupset a b c c a, x \sqsupset y \Longleftrightarrow x a \sqsupset y a\)
-
各大算法分析：
-
NAIVE（Brute-force）：就是普通的遍历
-
RK（Rabin-Karp算法）：用哈希表来进行运算，期望是：\(O(n)+O(m(v+n/q))\)
\(O(n/q)\)：哈希冲突的期望次数
v：有效偏移的数目 $$ \begin{aligned} & \operatorname{RABIN-KARP-MATCHER}(T, P, d, q) \ & n=\text { T.length } \ & m=P \text {.length } \ & h=d^{m-1} \bmod q \ & p=0 \ & t_0=0 \ & \text { for } i=1 \text { to } m \quad / / \text { Preprocessing } \ &\qquad p=(d p+P[i]) \bmod q \ & \qquad t_0=\left(d t_0+T[i]\right) \bmod q \ &\text { for } s=0 \text { to } n-m \quad / / \text { Matching }\ &\qquad \text { if } p==t_s\ &\qquad \qquad \text { if } P[1 . . m]==T[s+1 . . s+m]\ &\qquad \qquad \qquad \text { print "Pattern occurs with shift" s}\
&\qquad\text { if } s<n-m\ &\qquad\qquad t_{s+1}=\left(d\left(t_s-T[s+1] h\right)+T[s+m+1]) \bmod q\right.\
\end{aligned} $$
-
FA（ Finite automata 有限自动机）就是构建了一个自动机，来处理。缺点是与处理成本比较高。
第k个状态的含义：匹配了几个字符
用前缀函数改进可以改进到\(O(m|\Sigma|)\)
计算前缀的函数（复杂度：\(\Theta(m)\)）
-
KMP算法（Knuth-Morris-Pratt）
用前缀函数表来进行查找优化。只用进行两步：构建\(\pi\)表，开始搜索算法。
时间复杂度为\(O(m+n)\)
-
Boyer-Moore 算法主要依赖于两种启发式方法
坏字符规则、好后缀规则
预处理：
坏字符表：为模式中的每个字符确定其在模式中从右向左看的最后出现的位置。
好后缀表：预处理模式以找到每个后缀的最后出现位置，如果完整的后缀未在模式中其他地方出现，则找到部分匹配的最右端位置。 $$ b m B c[c]=\left{\begin{array}{l} \min {i: 1 \leq i \leq m-1 \text { and } P[m-i]=c} &\text { if } c \text { occurs in } P \ m & \text { otherwise. } \end{array}\right. $$
重叠后缀函数：以p[i]为后缀结尾的子串是否是全字符串后缀，该子串的最大长度 $$ \text { Osuff }[i]=\max {k: P[i-k+1 . . i]=P[m-k+1 . . m]} $$
参考例子（课件最后两个）
- AT-THAT
A T H - bmBc 1 3 2 4 A T - T H A T Osuff 0 2 0 1 0 0 7 bmGs 7 7 7 7 7 7 bmGs 5 5 5 5 5 7 7 bmGs 5 5 5 5 5 3 1 - AGAGTAGAG
A G T bmBc 1 2 4 A G A G T A G A G Osuff 0 2 0 4 0 0 2 0 9 bmGs 9 9 9 9 9 9 9 9 9 bmGs 5 5 5 5 5 7 7 9 9 bmGs 5 5 5 5 5 7 2 9 1 搜索过程：模式从文本的末端开始比较：
- 如果模式的最后一个字符与当前文本字符匹配，则继续向左比较直至不匹配或整个模式匹配完成。
- 如果发生不匹配，使用坏字符规则和好后缀规则中提供的最大跳跃来移动模式。
- 这种从右到左的匹配方式和根据文本中的实际字符来决定跳跃距离的策略，显著提高了搜索效率，特别是当模式较长或字符集较大时。
最坏情况：\(O(mn)\)；平均情况：\(O(n/m)\)
9. NPC
- P问题：可以在多项式时间内解决的问题
NP问题：可以在多项式时间被验证给出一个问题解的证书，在多项式时间内判断这个证书是否是问题的解
NPC问题：1.是NP问题2.所有NP问题都可以归约到该问题
NP hard问题：只满足”所有NP问题都可以归约到该问题“，并不确定是不是NP问题
- 规约：一个可以在多项式时间内完成的过程，将A的实例转化为B的实例而且具有相同的解，则称A归约到B。A的难度低于B。
（A正确则B正确、B正确则A正确。或A正确则B正确，A不正确则B不正确）
- 若 \(P_2\) 是 \(\mathcal{P}\) 问题，则 \(P_1\) 也是 \(\mathcal{P}\) 问题。
- 若 \(P_2\) 是 \(\mathcal{NP}\) 问题，则 \(P_1\) 也是 \(\mathcal{NP}\) 问题。
- 若 \(P_1\) 不是 \(\mathcal{P}\) 问题，则 \(P_2\) 也不是 \(\mathcal{P}\) 问题。
-
若 \(P_1\) 不是 \(\mathcal{N} \mathcal{P}\) 问题，则 \(P_2\) 也不是 \(\mathcal{N} \mathcal{P}\) 问题。
-
证明一个问题是NPC问题：
-
证明该问题是NP问题：可以在多项式时间内验证
-
把一个已知的NPC问题归约到这个问题
-
规约证明过程举例：
-
SAT到3-SAT
3-SAT 问题
问题描述： 给定一个布尔公式（每个子句有恰好三个文字），判断是否存在变量的真值赋值使得整个公式为真。
证明 3-SAT 是 NPC 的：
- Step 1: 证明 3-SAT 是 NP 问题：
- 对于一个给定的真值赋值，我们可以在多项式时间内检查每个子句是否至少有一个为真的文字，从而验证整个公式是否为真。因此，3-SAT 是一个 NP 问题。
- Step 2: 归约一个已知的 NPC 问题到 3-SAT：
- 从 SAT 问题（布尔可满足性问题）归约到 3-SAT。SAT 是第一个被证明为 NPC 的问题。任何 SAT 问题的实例都可以通过引入辅助变量和拆分大于三个文字的子句来转换为 3-SAT 形式。
- 归约过程：将每个包含超过三个文字的子句转换为多个包含恰好三个文字的子句，通过引入新变量和额外的限制条件（辅助子句）保持等价性。这样，原始 SAT 问题可满足当且仅当转换后的 3-SAT 问题可满足。
-
3-SAT到Hamiton
问题描述：
3-SAT问题： 给定一个布尔公式（每个子句有恰好三个文字），判断是否存在变量的真值赋值使得整个公式为真。
哈密顿回路问题： 给定一个图，确定这个图是否包含一个哈密顿回路，即访问图中每个顶点恰好一次的闭环路径。
证明 哈密顿回路 是 NPC 的：
- Step 1: 证明 哈密顿回路 是 NP 问题：
- 对于哈密顿回路，如果给定一个路径，我们可以在多项式时间内验证这条路径是否访问了每个顶点恰好一次并形成一个闭环。因此，哈密顿回路是一个 NP 问题。
- Step 2: 从 3-SAT 归约到 哈密顿回路：
- 归约过程：
- 构建过程：为每个 3-SAT 公式中的变量和每个子句构建图的一部分。
- 对于每个变量 \(x\)，构建一个包含两个路径的小图：一个路径代表 \(x\)，另一个代表 \(\neg x\)。这两条路径将交替连接，确保在任何哈密顿回路中，只有一条路径被完全遍历，从而在逻辑上选择了\(x\) 或 \(\neg x\)。
- 对于每个子句（如 \(x∨y∨z\)），构建一个连接这三个变量路径的“选择点”，确保如果子句为真（即至少一个变量选择使子句为真），则存在一条通过这个“选择点”的路径。
- 整合：将所有这些构建的路径和选择点组合成一个大图。
- 如果原始的 3-SAT 问题可满足，则在构建的图中可以找到一个哈密顿回路；如果 3-SAT 问题不可满足，则在图中找不到哈密顿回路。
-
3-SAT到团问题
问题描述：
团问题： 给定一个图和一个数 kkk，判断图中是否存在一个大小至少为 kkk 的团，即图中的一个顶点子集，其中任意两个顶点间都有边。
证明 团问题 是 NPC 的：
- Step 1: 证明 团问题 是 NP 问题：
- 对于团问题，如果给定一个顶点集，我们可以在多项式时间内验证这个集合中的每对顶点是否都相互连接，因此团问题是一个 NP 问题。
- Step 2: 从 3-SAT 归约到 团问题：
- 构建过程：
- 对于 3-SAT 公式中的每个子句，为每个文字创建一个顶点。
- 在两个顶点间添加一条边，当且仅当这两个顶点代表的文字不是对立的（即不是同一个变量的正面和反面）。
- 归约逻辑：
- 设 k 等于公式中子句的数量。
- 如果 3-SAT 公式可满足，则可以从每个满足的子句中选择一个文字，形成一个大小为 k 的团，因为选出的每对文字都不会互相矛盾。
- 反之，如果可以在构建的图中找到一个大小为 k 的团，那么这个团对应的文字集合将满足原始的 3-SAT 公式。
-
3-SAT到顶点覆盖问题
问题描述：
顶点覆盖问题： 给定一个图和一个数 k，判断图中是否存在一个包含至少 k 个顶点的顶点覆盖，即一个顶点集合，使得图中的每条边至少有一个端点在这个集合中。
证明 顶点覆盖问题 是 NPC 的：
- Step 1: 证明 顶点覆盖问题 是 NP 问题：
- 对于顶点覆盖问题，如果给定一个顶点集，我们可以在多项式时间内验证图中的每条边是否至少有一个端点在该集合中，因此顶点覆盖问题是一个 NP 问题。
- Step 2: 从 3-SAT 归约到 顶点覆盖问题：
- 构建过程：
- 构建图，为每个文字创建一个顶点，为不冲突的文字对添加边。
- 归约逻辑：
- 通过选择与每个子句相关联的文字节点构建顶点覆盖，确保覆盖每个代表子句内部矛盾（即文字对立）的边。
- 如果 3-SAT 公式可满足，则可以选择一个满足公式的变量赋值对应的顶点集作为顶点覆盖。
-
顶点覆盖问题到团问题
问题描述：
顶点覆盖问题： 给定一个图和一个数 k，判断图中是否存在一个顶点集合，使得图中的每条边至少有一个端点在这个集合中。
团问题： 给定一个图和一个数 k，判断图中是否存在一个顶点集合，其中任意两个顶点间都有边。
证明 团问题 是 NPC 的：
- Step 1: 证明 团问题 是 NP 问题：
- 对于团问题，如果给定一个顶点集，我们可以在多项式时间内验证集合中的每对顶点是否都相互连接，因此团问题是一个 NP 问题。
- Step 2: 从 顶点覆盖问题 归约到 团问题：
- 构建过程：
- 给定一个顶点覆盖问题实例，构建其补图，即在原图中不相连的顶点在补图中相连，反之亦然。
- 归约逻辑：
- 设原图中的顶点覆盖大小为 k，则其补图中的团大小至少为 n−k（其中 n 是图中顶点的总数）。这是因为顶点覆盖中未被选中的顶点在补图中构成一个团。
- 因此，如果我们可以在补图中找到一个大小为 n−k 的团，那么原图中存在一个大小为 k 的顶点覆盖。
-
顶点覆盖问题到Hamiton
问题描述：
顶点覆盖问题： 给定一个图 G(V,E) 和一个整数 k，判断是否存在一个顶点集合 V′⊆V，大小至多为 k，使得图中的每条边至少有一个端点在这个集合中。
哈密顿回路问题： 给定一个图，确定这个图是否包含一个哈密顿回路，即访问图中每个顶点恰好一次的闭环路径。
证明 哈密顿回路 是 NPC 的：
- Step 1: 证明 哈密顿回路 是 NP 问题：
- 对于哈密顿回路，如果给定一个路径，我们可以在多项式时间内验证这条路径是否访问了每个顶点恰好一次并形成一个闭环。因此，哈密顿回路是一个 NP 问题。
- Step 2: 从 顶点覆盖问题 归约到 哈密顿回路：
- 归约过程：
- 构建过程：从给定的图 G(V,E)出发，构建一个新图 G′。对于每个顶点 v 在 G，在 G′ 中添加两个顶点 v1 和 v2 和一条边 (v1,v2)。对于每条边 (u,v) 在 G 中，添加两条边 (u2,v1) 和 (v2,u1) 在 G′ 中。
- 整合：这种构建方式确保如果在 G′ 中存在一个哈密顿回路，那么在原图 G 中每个顶点 v 的两个副本 v1 和 v2 要么都在哈密顿回路中，要么都不在。这样的路径确保了从任一顶点的副本到另一顶点的副本的路径遍历了所有连接这两个顶点的边，从而覆盖了所有边。
- 逻辑：如果在 G′ 中找到哈密顿回路，则在 G 中存在一个顶点覆盖集合，其大小为哈密顿回路中每对相连顶点的一半，因为每对顶点 v1,v2 只需要选择一个加入顶点覆盖集合即可覆盖与 v 相关的所有边。反之，如果 G 中存在一个大小为 k 的顶点覆盖，则 G′ 中可以构建一个哈密顿回路，使得每个选中顶点的副本都连续地位于路径上，从而形成闭环。
-
Hamiton到TSP
旅行商问题 (TSP)
问题描述： 给定一个城市列表和每对城市之间的距离，找到一条最短的可能路径，让销售员访问每个城市恰好一次并返回起点。
证明 TSP 是 NPC 的：
- Step 1: 证明 TSP 是 NP 问题：
- 对于 TSP，如果给定一个路径，我们可以在多项式时间内验证这条路径是否访问了每个城市恰好一次并返回起点，以及这条路径的总距离是否为给定值。因此，TSP 是一个 NP 问题。
- Step 2: 归约一个已知的 NPC 问题到 TSP：
- 可以从 哈密顿回路问题（Hamiltonian Cycle Problem）归约到 TSP。哈密顿回路问题是一个已知的 NPC 问题，它要求找到一个图中是否存在一条访问每个顶点恰好一次并返回起点的循环路径。
- 归约过程：给定一个哈密顿回路问题的实例，我们构造一个 TSP 问题，其中每两个城市间的距离对应于原始图中两个顶点是否直接相连。如果两个顶点直接相连，距离为 1；如果不相连，距离为一个非常大的数（足够大以确保它不会出现在最短路径中）。如果存在哈密顿回路，则对应的 TSP 问题的最短路径长度将等于城市的数量；反之，如果 TSP 问题的解大于城市数量，原问题中不存在哈密顿回路。
-
已知的几个NPC问题（考试中可以进行规约使用的）
-
电路可满足性问题（Circuit Satisfiability Problem, CSAT）
这是一个决定性问题，询问是否存在一组输入使得布尔电路输出为真。布尔电路由逻辑门（如 AND、OR、NOT）构成，每个门有一个或多个输入和一个输出。电路可满足性问题是理解电路设计和逻辑设计自动化中的基础问题，同时也是第一个被证明为 NP 完全的问题。
- 公式可满足性问题（Satisfiability Problem, SAT）
SAT 是判断一个给定的布尔公式是否存在一种真值赋值使得整个公式为真的问题。布尔公式是由变量、逻辑运算符（AND, OR, NOT）和括号组成的表达式。这是一个核心的逻辑问题，在计算机科学的很多领域中都有广泛应用，例如在软件验证、人工智能和数据库理论中。
- 三合取范式问题（3-Satisfiability Problem, 3-SAT）
3-SAT 是 SAT 的一个特殊情况，其中每个子句恰好包含三个文字（变量或其否定）。尽管这个限制看起来更严格，3-SAT 仍然是 NP 完全的。它经常被用作其他 NP 完全问题的归约基础，因为它简化了归约的逻辑结构。
- 团问题（Clique Problem）
团问题要求确定一个无向图中最大团的大小，或判断图中是否存在至少包含 k 个顶点的团。团是一个顶点子集，其中任意两个顶点之间都有边相连。这个问题在社交网络分析、生物信息学和通信网络中有重要应用。
- 顶点覆盖问题（Vertex Cover Problem）
顶点覆盖问题是指找到图中最小的顶点集合，使得图中的每条边至少有一个端点在这个集合中。这个问题在网络设计、资源分配和生态学研究中非常重要。
- 哈密顿回路问题（Hamiltonian Cycle Problem）
哈密顿回路问题是判断一个给定的图是否包含一个哈密顿回路，即一个访问每个顶点恰好一次并返回起点的闭合路径。这个问题对于理解图的结构和解决路由问题具有基本意义。
- 旅行商问题（Traveling Salesman Problem, TSP）
旅行商问题要求找到一个最低成本的哈密顿回路，即访问图中每个顶点恰好一次后返回起点的路径，且路径的总成本最小。这是运筹学和逻辑优化中的一个经典问题，广泛应用于物流和调度领域。
值得指出的是这几个是逐层变难的，即上能归约到下，相关的证明如上都有给出。
10. 近似算法
-
我们说一个问题的算法具有近似比率 \(\rho(n)\) ，如果对于任何大小为 \(n\) 的输入，该算法产生的解的成本 \(C\) 与最优解的成本 \(C^*\) 之间的比值满足以下条件: $$ \max \left(\frac{C}{C^}, \frac{C^}{C}\right) \leq \rho(n) . $$
-
三类近似模式：
- 优化问题的近似方案是一种近似算法，它不仅接受问题的一个实例作为输入，还接受一个值 \(\epsilon>0\), 使得对于任何固定的 \(\epsilon\) ，该方案都是一个 \((1+\epsilon)\)-近似算法。
- 如果对于任何固定的 \(\epsilon>0\) ，该方案的运行时间是输入实例大小 \(n\) 的多项式时间，我们称这种近似方案为多项式时间近似方案 (PTAS)。
-
如果近似方案的运行时间既是 \(\frac{1}{\epsilon}\) 的多项式，也是输入实例大小 \(n\) 的多项式，我们称这种近似方案为完全多项式时间近似方案 (FPTAS)。 例如，该方案的运行时间可能为 \(O\left(\left(\frac{1}{\epsilon}\right)^2 n^3\right)\) 。.
-
近似算法的几个例子
-
顶点覆盖问题（The vertex cover） $$ \begin{aligned} &\text { APPROX-VERTEX-COVER(G) }\ & C=\emptyset\ &E^{\prime}=G . E\ &\text { while } E^{\prime} \neq \emptyset\ &\quad\quad\text { let }(u, v) \text { be an arbitrary edge of } E^{\prime}\ &\quad\quad C=C \cup{u, v}\ &\quad\quad\quad\text { remove from } E^{\prime} \text { every edge incident on either }u \text{or} v\ & \text { return } C \end{aligned} $$
算法基本思路：复制G的边集到E'，从E‘中随机选取边uv，移除所有与uv相连的边，直至E’为空
\(O(V+E)\)
近似比为2。
-
旅行商问题（TSP）
算法的基本思路：先构建一个最小生成树，进行前序遍历，返回哈密顿回路。
近似比为2。\(\Theta(V^2)\)
-
集合覆盖问题（Set-Covering Problem）
算法的基本思路：迭代选择覆盖未覆盖元素最多的子集，直到所有元素都被覆盖。 $$ \begin{array}{ll} & GREEDY-SET-COVER (X, \mathcal{F})\ 1 & U=X \ 2 & \mathcal{C}=\emptyset \ 3 & \text { while } U \neq \emptyset \ 4 & \qquad \text { select an } S \in \mathcal{F} \text { that maximizes }|S \cap U| \ 5 & \qquad U=U-\mathcal{S} \ 6 &\qquad \mathcal{C}=\mathcal{C} \cup{S} \ 7 & \text { return } \mathcal{C} \end{array} $$ 时间复杂度：O(|X||F| min(|X|, |F|).
近似比为log|X|+1
是一种多项式时间近似方案
-
最大化3-SAT问题
问题描述：最大化一个3-CNF布尔公式中满足的子句数量。
最终的期望近似比为8/7
-
LP问题（最小权值顶点覆盖问题）
$$ \begin{aligned} &\text { APPROX-MIN-WEIGHT-VC(G, w) }\ & C=\emptyset\ & \text { compute } \bar{x} \text {, an optimal solution to the linear program.}\ &\text { for each } v \in V\ &\qquad \text { if } \bar{x}(v) \geq 1 / 2\ &\qquad \qquad C=C \cup{v}\ &\text { return } \mathrm{C} \end{aligned} $$ 2近似比
-
子集和问题SubSet-sum problem
算法思路：尝试找到一个最接近但不超过目标值 t 的子集和。算法使用了动态规划的思想，并通过精心设计的修剪步骤来保持问题的可管理性，从而在多项式时间内给出一个与最优解非常接近的结果。
关键点是\(\epsilon\)的选取 $$ \begin{aligned} &\text { APPROX-SUBSET-SUM }(S, t, \epsilon)\ & n=|S|\ &L_0=\langle 0\rangle\ &\text { for } i=1 \text { to } n\ &\qquad L_i=\operatorname{MERGE} \operatorname{LISTS}\left(L_{i-1}, L_{i-1}+x_i\right)\ &\qquad L_i=\operatorname{TRIM}\left(L_i, \epsilon / 2 n\right)\ &\qquad \text { remove from } L_i \text { every element that is greater than }t\ &\text { let } z^ \text { be the largest value in } L_n\ &\text { return } z^ \end{aligned} $$ 是一个完全多项式时间的近似算法
-
通用技术：证明某一问题无法被很好地近似。给定NP难的问题\(X\), 可以在多项式时间内构造出最小化问题 \(Y\), s.t. X的yes实例对应值至多为 \(k\) 的 \(Y\) 实例, no实例对应值大于 \(\rho k\) 的 \(Y\) 实例。因此证明了：除非 \(\mathrm{P}=\mathrm{NP}\), 否则问题 Y不存在多项式时间内的 \(p\) 近似算法。
11. 多线程算法
- 关键词：
spawn：开启一个派生子进程, 这个进程将会和父进程同时运行。父进程不必等子进程计算完 sync：等待上面所有派生的子进程都运行完毕后再执行接下来的代码。父进程至此才能安全地使用派生子进程的返回值 parallel: 并发关键字, 实现循环井发执行的迭代
- 性能提升：
work law：\(T_p \geq T_1 / P\)
span law：\(T_p \geq T_{\infty} .\)
speedup ：\(T_1 / T_p .\)
Iinear speedup :\(T_1 / T_p=\Theta(P) .\)
perfect linear speedup :\(T_1 / T_p=P .\)
Theorem：\(T_p \le T_1/P+T_{\infty}\)
并行性parallelism :\(T_1 / T_{\infty} .\)
松弛度：\((T_1 / T_{\infty}) /P\) （随着松弛度的增长，任何多线程计算都可以在贪心调度下达到完美线性。）
-
例子
-
斐波那契数列
- 矩阵和向量乘法的多线程递归算法Multiplying matrix by and vector
- 矩阵乘法的多线程法
指出这种算法\(T_{\infty}=\Theta(n)\)则并行度为\(\Theta(n^2)\)
这种算法的思路是拆分成子矩阵，且用D来存多余加法。
这样的\(T_{\infty}=\lg ^2n\)，并行度为\(\Theta(n^3/\lg ^2 n)\)
- 归并排序
粗略地看\(T_{\infty}=\Theta(n)\)则并行度为\(\Theta(\lg n)\)
但是实际上：
一些例题
解递归式
如果能用主定理，背熟主定理，不能用要么转换形式到主定理，要么找规律
- ==\(T(n)=2T(\frac{n}{4})+\sqrt{n}\)==
解：由主方法的递归定理即可知，\(a=2,b=4,f(n)=\sqrt{n},n^{\log_ba}=n^{\log_42}=\sqrt{n}=f(n)\)，
即可知其满足主定理的第二种情况：\(f(n)=\Theta(n^{\log _ba})\)
则有：\(T(n)=\Theta(\lg n \sqrt{n})\)
- ==\(T(n)=2T(\sqrt{n})+1\)==
解：由于此时不满足\(T(n) = aT( \frac {n}{b} )+ f(n)\)的形式，于是需要进行适当的变换。
令\(t=\lg n,n=2^t\)，代入则有：\(T(2^t)=2T(2^{\frac{t}{2}})+1\)
为了简化表述，我们设：\(S(t) = T(2^t)\)，则上式变为：
\(S(t) = 2S(\frac{t}{2}) + 1\)
此时这种形式是符合主方法的，有\(f(t)=1,a=2,b=2,t^{\log_ba}=t^{\log_22}=t^1\)
有\(f(t)=O(n^{\log _ba-\varepsilon})\)，其中\(\varepsilon\)可取\((0,1)\)中任一常数。
即可知其满足主方法的第一种情况，则有：\(S(t)=\Theta(t)\)
由于\(S(t) = T(2^t),t=\lg n\)，则有：\(T(n)=T(2^t)=S(t)=\Theta(t)=\Theta(\lg n)\)
综上所述：\(T(n)=\Theta(\lg n)\)
- ==\(nT(n) = (n−2)T(n−1) + 2\)==
解：分析即可知其很难直接使用主方法来进行递归解决，但是可以尝试进行找规律来分析。
可以计算前几项来分析一下其在n较小的时候的复杂度：
当 \(n=2\) 时，\(2T(2) = (2-2)T(1) + 2=0\cdot c+2=2\)，得到 \(T(2) = 1\)。
当 \(n=3\) 时，\(3T(3) = (3-2)T(2) + 2 = 1 \cdot 1 + 2 = 3\)，得到 \(T(3) = 1\)。
当 \(n=4\) 时，\(4T(4) = (4-2)T(3) + 2 = 2 \cdot 1 + 2 = 4\)，得到 \(T(4) = 1\)。
于是我们可以推测当 \(n \ge 2,T(n) = 1\)，接下来用数学归纳法来严格证明：
已知\(T(2)=1\)，假设对于某个 \(k \ge 2\)，有 \(T(k) = 1\)，仅需证明\(T(k + 1) = 1\) 也成立。
由于：$ (k+1)T(k+1) = (k-1)T(k) + 2 =k+1\(，得到\)T(k + 1) = 1$ ，得证，则假设成立。
综上所述：\(T(n)=1~~~(n\ge 2)\)
快排中对PARTITION算法的优化（增加相等区间）
在7.4.2节对随机化快速排序的分析中，我们假设输入元素的值是互异的，在本题中，我们看看如果这一假设不成立会出现什么情况。
a. 如果所有输入元素的值都相同，那么随机化快速排序的运行时间会是多少？
b. \(PARTITION\)过程返回一个数组下标\(q\)，使得\(A[p..q-1]\)中的每个元素都小于或等于\(A[q]\)，而\(A[q+1..r]\)中的每个元素都大于\(A[q]\)。修改\(PARTITION\)的代码来构造一个新的\(PATITION'(A,p,r)\)，它排列\(A[p..r]\)的元素，返回值是两个数组下标\(q\)和\(t\)，其中\(p\le q\le t \le r\)，且有
- \(A[q..t]\)中的所有元素都相等。
- \(A[p..q-1]\)中的每个元素都小于\(A[q]\)。
- \(A[t+1..r]\)中的每个元素都大于\(A[q]\)。
与\(PARTITION\)类似，新构造的\(PATITION'\)的时间复杂度是\(\Theta(r-p)\)。
c. 将\(RANDOMIZED-QUICKSORT\)过程改为调用\(PARTITION'\),并重新命名为\(RANDOMIZED-QUICKSORT'\)。修改\(QUICKSORT\)的代码构造一个新的\(QUICKSORT’(A,p,r)\)，它调用\(RANDOMIZSE-PARTITION'\)，并且只有分区内的元素互不相同的时候才做递归调用。
d. 在\(QUICKSORT'\)中，应该如何改变 7.4.2 中的分析方法，从而避免所有元素都是互异的这一假设？
==a.==
当由于所有的输入元素的值都相同，所以\(RANDOMIZED-QUICKSORT\)过程总是会返回\(q=r\)这一结果。
因此有递归式 $$ T(n)=T(n-1)+\Theta(n) $$ 可以得出 $$ T(n)=\Theta(n^2) $$ 因此其运行时间的时间复杂度为\(\Theta(n^2)\)
==b.==
经分析，\(PATITION'(A,p,r)\)的伪代码如下：
1: \(x=A[r]\) 2: \(q=r\) 3: \(t=r\) 4: for \(j=r-1\) to \(p\) 5: if \(A[j]>x\) then 6: \(q=q-1\) 7: \(t=t-1\) 8: \(exchange~A[j]~with~A[q]\) 9: \(exchange~A[q]~with~A[t+1]\) 10: else if \(A[j]==x\) then 11: \(q=q-1\) 12: \(exchange~A[j]~with~A[q]\) 13: return \((q,t)\)
此时，相较于旧的\(PARTITION\)算法，通过新建了一个等于基准元素的新分区，来减少不必要的比较和交换操作，从而提高排序过程的效率。
==c.==
经分析，\(QUICKSORT'(A,p,r)\)的伪代码如下：
1: if \(p<r\) 2: \((q,t)=RANDOMIZED-PARTITION'(A,p,r)\) 3: \(QUICKSORT'(A,p,q-1)\) 4: \(QUICKSORT'(A,r+1,r)\)
==d.==
我们对传统的\(PARTITION\)进行的优化是，将原有的分区新增到三个分区：小于基准、等于基准、大于基准。这样就避免了等于基准区域元素的比对和交换。
这样的优化减少了\(QUICKSORT\)中子问题的数量，因此时间复杂度也不会高于原算法。
因此，合理地避免所有元素都是互异的这一假设。
桶排序问题的实践
在单位圆内给定 \(n\) 个点，\(p_i=(x_i,y_i)\)，对所有的\(i=1,2,\cdots,n\)，有\(0<x_i^2+y_i^2\le 1\)。假设所有点服从均匀分布，即在单位元的任一区域内找到给定点的概率与该区域的面积成正比。
请设计一个在平均情况下有\(\Theta(n)\)时间复杂度的算法，它能够按照点到原点之间的举例\(d=\sqrt{x_i^2+y_i^2}\)对这\(n\)个点进行排序。
（提示：在\(BUCKET-SORT\)中，设计适当的桶的大小，用以反映各个点在单位元中分布均匀的情况。）
解：
由于需要==点出现在一个区域的概率与面积成正比==
所以可以将单位圆根据面积分为\(n\)份，即一个一个同面积的圆环，我们记它们为： $$ B[0],B[1],B[2],\cdots,B[n-1], $$ 根据集合关系分析也可知，点\(p_i=(x_i,y_i)\)所在区域满足关系： $$ B[\lfloor{\frac{x_i^2+y_i^2}{1^2+1^2}\times n}\rfloor]=B~[~\lfloor(x_i^2+y_i^2)n\rfloor~] $$ 所以现在就设计出了一个均匀的桶，其桶的大小均为==所占面积为\(1/n\)==，由于点服从均匀性分布，所以每个桶内的点的个数平均个数为1。
时间复杂度分析
-
分配点到桶中的时间：\(\Theta(n)\)，由于每个点只需要计算一次距离，再分到桶里面。
-
桶内排序的时间：\(\Theta(n)\)，从平均上看，每个桶内的点的个数平均为1，因此每个桶的排序时间为\(\Theta(1)\)，由于有\(n\)个桶，因此总的为\(\Theta(n)\)，得证。
-
合并桶：\(\Theta(n)\)，由于只需要将每个元素按照桶的顺序放入
result数组即可，因此也是\(\Theta(n)\)。
最终合并可知，其平均情况下时间复杂度为\(\Theta(n)\)，得证。
伪代码部分 \(Annulus-Bucket-Sort(P)\) $$ \begin{align} 1.& \qquad\qquad\qquad n = \text{length}(P) \ 2.& \qquad\qquad\qquad \text{Initialize array } B[0 \ldots n-1] \ 3.& \qquad\qquad\qquad \textbf{for } i = 1 \textbf{ to } n \textbf{ do} \ 4.& \qquad\qquad\qquad \qquad index = \left\lfloor (x_i^2 + y_i^2) \cdot n \right\rfloor \ 5.& \qquad\qquad\qquad \qquad \text{Insert } P[i] \text{ into } B[index] \ 6.& \qquad\qquad\qquad \textbf{for } i = 0 \textbf{ to } n-1 \textbf{ do} \ 7.& \qquad\qquad\qquad \qquad \text{Sort } B[i] \ 8.& \qquad\qquad\qquad P = \text{merge all lists in } B \quad \ \end{align} $$
K-分位数问题
对一个包含 \(n\) 个元素的集合来说，\(k\) 分位数是指能把有序集合分成\(k\)个等大小集合的第\(k-1\)个顺序统计量。给出一个能找到某一集合的\(k\)分位数的\(O(n\lg k)\)时间的算法。
解：
经分析，本算法的要求是找到某一集合的\(k\)个分位数，可以将集合分割成\(k\)个具有相同大小的连续子集。
算法步骤：
- 预计算分位数的位置
计算每个分位数在已排序数组中的理论位置。这一步的时间复杂度为\(O(k)\)，因为一旦数组被排序，每个分位数的位置就可以通过简单的算术运算确定。
- 使用选择算法快速找到中位数
利用快速选择（\(QuickSelect\)）算法，其时间复杂度为\(O(n)\)。但是其只能找到特定顺序统计量的部分进行排序。因此可以使用它来找到中位数，即$\lfloor \frac{k}{2} \rfloor $。
- 递归地在两个子集中找其他分位数
首先使用快速选择算法找到\(\lfloor \frac{k}{2} \rfloor\)的分位数（即中间分位数），这将数组分成两个子集。然后，我们递归地在每个子集中寻找\(\frac{k}{2}-1\)个分位数（对于左侧子集）和\(\frac{k}{2}\)个分位数（对于右侧子集）。通过这种方式，每次递归都会将搜索范围减半，并且每个分位数都能够在其对应的子集中被找到。
算法时间复杂度分析
由于需要找到\(k\)个分位数，在递归地寻找下，平均地看，其问题会有\(\lg k\)层递归。
对每层进行分析，对于第一层，其时间复杂度为快速选择复杂度\(O(n)\)；对于第二层，其时间复杂度为\(2\times O(\frac{n}{2})=O(n)\)。以此类推，可以知道，每层的时间复杂度预期均为\(O(n)\)。
于是本算法的总时间复杂度为\(O(n\lg k)\)，符合题意。
算法的伪代码
- \(FindKthQuantiles(A, k)\)
总函数部分：创建一个新数组 \(Quantiles\) 来存储 $ k−1$ 个分位数，并通过调用 \(Select\) 函数在适当的位置找到每个分位数。
- $ Select(A, k, left, right)$
此函数是快速选择算法的核心，用于找到数组 \(A\)中第\(k\) 小的元素。
- $ Partition(A, left, right)$
此函数用快速选择算法数组对数组分区并返回\(pivotIndex\)。
动态规划关于钢条切割的深化
我们对钢条切割问题进行一点修改，除了切割下的钢条段具有不同价格\(p_i\)外，每次切割还要付出固定的成本\(c\)。这样，切割方案的收益就等于钢条段的价格之和减去切割的成本。设计一个动态规划算法解决修改后的钢条切割问题。
解：
即在每一次迭代中考虑成本\(c\)，再依次进行迭代计算
伪代码部分 \(New-Cut-Rod(p,n,c)\) $$ \begin{align} 1.& \qquad\qquad\qquad \textbf{new ~an~anrry~}r[0..n] \ 2.& \qquad\qquad\qquad r[0]=0 \ 3.& \qquad\qquad\qquad \textbf{for } i = 1 \textbf{ to } n \textbf{ do} \ 4.& \qquad\qquad\qquad \qquad q=p[i] \ 5.& \qquad\qquad\qquad \qquad\textbf{for } j = 0 \textbf{ to } i-1 \textbf{ do}\ 6.& \qquad\qquad\qquad \qquad\qquad q=max(q,p[j]+r[i-j]-c) \ 7.& \qquad\qquad\qquad \qquad r[i]=q \ 8.& \qquad\qquad\qquad \textbf{return}~~r[n] \ \end{align} $$
伪代码中，我们在每一次内循环考虑成本 \(c\) （除了最后一次无切割时）。
然后再选择每次迭代中的最佳收益情况。
贪心的一个例子
假定有一组活动，我们需要将它们安排到一些教室，任意活动都可以在任意教室进行。我们希望使用最少的教室完成所有活动。设计一个高效的贪心算法求每个活动应该在哪个教室进行。
（这个问题称为区间图着色问题(interval-graph color problem)。我们可以构造一个区间图，顶点表示给定的活动，边连接不兼容的活动。要求用最少的颜色对顶点进行着色，使得所有相邻顶点颜色均不相同--这与使用最少的教室完成所有活动的问题是对应的。）
解：
算法步骤
-
输入活动集合：首先输入所有活动的列表，每个活动由一个开始时间和结束时间表示。
-
排序：将所有活动按照结束时间的早晚进行排序。如果两个活动结束时间相同，则可以任意排序或按开始时间排序。
-
初始化：初始化一个空的最小堆（或其他数据结构，如优先队列），用来存储正在使用的教室的结束时间。
-
分配教室：
- 对于每一个活动，检查堆中最早结束的教室（堆顶元素）是否可以用来进行这个活动。这可以通过比较堆顶元素的结束时间与当前活动的开始时间来决定。
- 如果当前活动的开始时间晚于或等于堆顶教室的结束时间，那么可以复用这个教室。更新这个教室的结束时间为当前活动的结束时间，并调整堆。
-
如果不能复用任何现有教室，即所有教室的结束时间都早于当前活动的开始时间，那么开启一个新的教室，并将其结束时间加入堆中。
-
结果：算法完成后，堆的大小即为所需的最小教室数，因为堆中存储了所有正在使用的教室的结束时间。
总结
这个贪心算法的核心在于，通过优先复用最早空出的教室，确保教室的利用率最大化，从而用最少的教室数满足所有活动。该算法的时间复杂度主要由排序活动决定，为 \(O(n \log n)\)；空间复杂度为 \(O(n)\)，因为需要存储所有教室的结束时间。
摊还分析的例子
假定一个数据文件由8位字符组成，其中所有256个字符出现的频率大致相同：最高的频率也低于最低频率的2倍。
证明：在此情况下，赫夫曼编码并不比8位固定长度编码更有效。
证明：
根据题设：对于任何两个字符，它们的频率之和超过任何其他字符的频率。
因此，在霍夫曼编码最初创建时，只会产生==128==个只有两个叶子的小树。
在下一个阶段，没有一个内部节点的标签是其他任何节点的两倍以上，所以我们处于与之前相同的设置中。
我们如此继续这样的过程，一共进行八次，
可以发现：霍夫曼编码构建了一个高度为 \(\(\log_2 256 = 8\)\) 的==完整二叉树==。
即可知：其效率不超过普通的8位固定长度编码，得证。
贪心算法证明总能找到最优解的例子
一眼能看出来就大白话说明，or归纳地来证明
考虑用最少的硬币找零 n 美分的问题。假定每种硬币的面额都是整数。
a. 设计一个贪心算法来解决美国的硬币系统问题，硬币面额有 25 美分、10 美分、5 美分和 1 美分 4 种面额的硬币。证明你的算法能得到最优解。
b. 假定硬币面额是 \(c\) 的幂，即面额为 \(\(c^0, c^1, \ldots, c^{k-1}\)\)，\(c^k\)为整数，且\(c>1,k\ge1\)，证明：贪心算法总能得到最优解。
c. 设计一组硬币面额，使得贪心算法不能保证得到最优解。这组硬币面额中应该包含1美分，使得每个零钱值都存在找零方案。
d. 设计一个 \(\(O(nk)\)\) 时间的找零算法，适用于任何 k 种不同面额的硬币，假定总是能给出 1 美分的硬币。
解
a.
算法：
- 从最大面额开始，计算可以使用多少个该面额的硬币，不使得总值超过需找的金额。
- 从需找的金额中减去已经使用的硬币的总值。
- 对剩余的金额重复步骤1和2，选择下一个最大面额的硬币。
- 重复此过程，直到找完所有的零钱。
证明：
如题：硬币的面额为 1 美分、5 美分、10 美分和 25 美分，这些面额都是==彼此之间的倍数==（1, 5, 10, 25）。
这意味着较大面额的硬币总是可以被较小面额的硬币数量整除
在这种系统下，贪心算法有效，因为最大面额的硬币总能包含较小面额硬币的整数倍，不会遗漏任何能被更大面额替代的找零方式。这个属性保证了在找零的过程中，每一步都尽可能使用最大的面额，不会导致找零的总硬币数增加。
b.
用归纳法证明：
基础情况
- 当 \(n = 0\) 时，不需要任何硬币，这与贪心策略相符。
- 当 \(1 \leq n < c\) 时，因为 \(c > 1\)，贪心策略会选择尽可能多的 \(c^0 = 1\) 面额硬币，即 \(n\) 个，这显然是最优解。
归纳步骤
假设对于所有小于 \(n\) 的找零量，贪心策略都给出了最优解。我们现在考虑找零量 \(n\)。
- 选取最大的 \(d\) 使得 \(c^d \leq n\)，贪心策略会首先使用一个 \(c^d\) 硬币。这样，我们剩下的找零量为 \(n - c^d\)。
- 由归纳假设，对于 \(n - c^d\)，贪心策略提供最优解。
- 因为我们已经选用了最大可能的硬币，剩余部分的解决也是最优的，因此整体策略也是最优的。
综上，得证。
c.
假设面额数量为：1，90，100。如果当零钱值为180时，通过本贪心算法计算所得的阵列为：100和80个1，n值为81。
但是正确的解应为2个90，即n为2。
通过上面这个例子即可知，存在零钱面额的情况使得贪心算法不满足。
d.
要设计一个 \(O(nk)\) 时间的找零算法，适用于任何 k 种不同面额的硬币，一个常用的方法是动态规划。这里的 n 是需找的金额，k 是硬币面额的种类数。
动态规划算法的基本思想是构建一个解的表，表中的每个条目代表找零金额 i（从 0 到 n）所需的最小硬币数。表是通过考虑每个可能的硬币面额来构建的，这样可以为每种金额找到一个最优解。算法的每个步骤如下：
- 创建一个大小为 n+1 的数组，用于保存每个金额所需的最小硬币数，初始化所有值为无穷大（除了金额 0，它需要 0 枚硬币）。
- 对于每个硬币面额 c，更新数组中所有金额为 i 的条目，其中 i 从 c 到 n。
- 每个数组条目的更新是基于前一个状态的最优解加上一个 c 面额的硬币。
- 最终，数组的最后一个条目就是找零 n 美分所需的最小硬币数。
由于这个算法中有两层嵌套循环（外层对于每个金额，内层对于每个硬币面额），它的时间复杂度是 \(O(nk)\)。
贪心证明与并查集的应用
对16.5节中带截止时间和惩罚的单位时间任务调度问题，考虑如下算法。初始时令\(n\)个时间槽均为空，时间槽\(i\)为单位时间长度，结束于时刻\(i\)。我们按惩罚值单调递减的顺序处理所有任务。当处理任务为\(a_j\)时，如果存在不晚于\(a_j\)的截止时间\(d_j\)的空时间槽，则将\(a_j\)分配到其中最晚的那个。如果不存在这样的时间槽，将\(a_j\)分配到最晚的空时间槽。
a.证明：此算法总能得到最优解。
b.利用21.3节提出的快速不相交集合森林来高效实现此算法。假定输入任务集合已经按惩罚值单调递减的顺序排序。分析实现程序的运行时间。
证明： a.
设 \(O\) 为一个最优解，可以将其分为三种情况分析：
- 如果任务 \(a_j\) 在其截止时间之前就被安排了，我们总是可以将它与在其截止时间被安排的任何任务交换，而不改变惩罚值。
- 如果 \(a_j\) 被安排在了截止时间之后，且 \(a_j.deadline \leq j\)，那么一定存在一个惩罚值小于 \(a_j\) 的任务在 \(j\) 之前被安排了。我们可以将 \(a_j\) 与这个惩罚值较小的任务交换，从而减少总惩罚。由于 \(O\) 是最优的，这种情况不会发生。
- 如果 \(a_j\) 被安排在了截止时间之后，并且 \(a_j.deadline > j\)，我们可以将 \(a_j\) 与任何其他较晚的任务交换，而不会增加惩罚值。
综上所述，此算法总能得到最优解，得证。
b.
算法关键操作：
算法核心依赖于不相交集合森林（Disjoint Set Forest），这是一种特别适合于管理不重叠集合的数据结构，实现了以下三个操作：
MAKE-SET：为每个新任务创建一个新的集合。FIND-SET：查找指定元素所在的集合的代表，这里用于确定任务可以放置的最晚时间槽。UNION：合并两个集合，用于将新任务的时间槽与相邻的已占用时间槽合并，维护时间槽的连续性。
每个集合的代表节点存储了两个关键属性：low 和 high，分别表示集合中所有任务的最早和最晚时间槽。通过这些属性，UNION 操作能够正确维护合并后集合的时间范围。
算法过程：
- 使用
FIND-SET操作确定任务截止时间对应的集合代表。 - 根据找到的集合代表的
high属性确定任务的调度时间为high + 1。 - 通过
MAKE-SET创建一个新的集合，并将任务添加到该时间槽。 - 更新时间槽的集合信息，设置
low和high属性为当前时间槽。 - 如果有相邻时间槽已安排任务，通过
UNION合并集合，确保时间槽连续性。
算法时间复杂度分析：
这种方法的时间复杂度主要受不相交集合操作影响。
因此：每个操作的平摊成本是 \(O(\alpha(n))\)（其中 \(\alpha(n)\) 是阿克曼函数的逆函数，它增长非常缓慢，使得实际运行时间近似为常数。）
因此，总的运行时间为 \(O(n \alpha(n))\)，表现出极高的效率。
伪代码如下：
SCHEDULING-VARIATIONS(A)
let D[1..n] be a new array
for i = 1 to n
D[i] = MAKE-SET(nil)
for i = 1 to n
if D[A[i].deadline] != NIL
x = FIND-SET(D[A[i].deadline])
A[i].time = x.high + 1
x = MAKE-SET(A[i])
D[A[i].time] = x
x.low = A[i].time
x.high = A[i].time
if D[A[i].time - 1] != NIL
UNION(D[A[i].time - 1], D[A[i].time])
if D[A[i].time + 1] != NIL
UNION(D[A[i].time], D[A[i].time + 1])
FA的构建算法设计
感觉大白话说也行……不需要什么伪码
给出一个有效算法，计算出相应于某给定模式\(P\)的字符串匹配自动机的转移函数\(\delta\)。所给出的算法的运行时间应该是\(O(m|\sum|)\)。
（提示：证明如果\(q=m\)或\(P[q+1]\ne a\)，则\(\delta(q,a)=\delta(\pi[q],a)\)）
解：
function compute_transition_function(P, Sigma):
m = length(P)
for q = 0 to m:
for a in Sigma:
if q < m and P[q+1] == a:
delta(q, a) = q + 1
else:
if q == 0:
delta(q, a) = 0
else:
delta(q, a) = delta(pi[q], a)
return delta
时间复杂度证明：
分析算法的时间复杂度涉及考察算法中每个部分的执行次数和执行代价。在我们的情况中，计算字符串匹配自动机的转移函数 \(\delta\) 是一个双重循环的过程，主要涉及两个参数：模式的长度 \(m\) 和字符集的大小 \(|\Sigma|\)。
外层循环：状态 \(q\)
外层循环遍历模式 \(P\) 的每个位置，从 \(q = 0\) 到 \(q = m\)，这里 \(m\) 是模式 \(P\) 的长度。因此，外层循环将执行 \(m+1\) 次。
内层循环：输入字符 \(a\)
对于每个状态 \(q\)，内层循环遍历字符集 \(\Sigma\) 中的每个字符 \(a\)。字符集的大小记为 \(|\Sigma|\)。因此，对于每个状态 \(q\)，内层循环将执行 \(|\Sigma|\) 次。
每次迭代的工作
在每次内层循环的迭代中，算法执行以下步骤：
-
检查条件：首先检查 \(P[q+1] == a\) 条件。这个条件的检查是 \(O(1)\) 的操作。
-
设置 \(\delta\) 函数：
- 如果 \(P[q+1] == a\) 成立，则 \(\delta(q, a) = q+1\)。
- 如果 \(P[q+1] \neq a\) 或者 \(q = m\)，则 \(\delta(q, a) = \delta(\pi[q], a)\)。
在设置 \(\delta\) 函数时，如果是第二种情况（即 \(P[q+1] \neq a\) 或者 \(q = m\)），则需要回溯到 \(\pi[q]\) 状态并查找对应 \(a\) 的转移。这一步是通过已计算好的 \(\delta\) 和 \(\pi\) 函数来实现的，因此也是 \(O(1)\) 的操作。
总的复杂度计算
将内层循环的操作累加起来，我们得到对每个 \(q\) 的所有 \(a\) 的迭代总和： $ (m+1) \times |\Sigma| $ 其中，\(m+1\) 是状态的数量（包括初始状态 0），而 \(|\Sigma|\) 是每个状态下需要处理的字符数。因此，总的负责度是 \(O(m|\Sigma|)\)。
摊还分析
有序数组上的二分查找花费对数时间，但插入一个新元素的时间与数组规模呈线性关系。我们可以通过维护多个有序数组来提高插入性能。
假定我们希望支持\(n\)元集合上的\(SEARCH\)和\(INSERT\)操作。令\(k=\lceil \lg(n+1)\rceil\)，令\(n\)的二进制表示为\(<n_{k-1},n_{k-2},\cdots,n_{0}>\)。我们维护\(k\)个有序数组\(A_0,A_1,\cdots,A_{k-1}\)，对\(i=0,1,\cdots,k-1\)，数组\(A_i\)的长度为\(2^i\)。每个数组或满或空，取决于\(n_i=1\)还是\(n_i=0\)。因此，所有\(k\)个数组中保存的元素总数为\(\sum^{k-1}_{i=0}n_i2^i=n\)。虽然单独每个数组都是有序的，但不同的数组中的元素之间不存在特定的大小关系。
a.设计算法，实现这种数据结构的\(SEARCH\)操作，分析其最坏情况运算时间
b.设计\(INSERT\)算法。分析最坏情况运行时间和摊还时间。
c.讨论如何实现\(DELETE\)
解：
a.
为了在这个数据结构上执行 \(SEARCH\) 操作，我们需要对每个非空数组 \(A_i\) 进行二分查找。
因为数组 \(A_i\) 的长度是 \(2^i\)，所以在数组 \(A_i\) 上进行一次二分查找的时间复杂度是 \(O(i)\)。
由于 \(i\) 的最大值是 \(k-1\)，所以在最坏情况下 \(SEARCH\) 操作的总时间复杂度是 ==\(O(\lg^2 n)\)==。
b.
对于 \(INSERT\) 操作，我们首先尝试将元素插入到数组 \(A_0\) 中。
如果 \(A_0\) 已满，则将 \(A_0\) 与 \(A_1\) 合并，并尝试将新元素（及可能的合并结果）插入 \(A_1\)，依此类推，直到找到一个空数组。
在最坏的情况下，我们可能需要合并所有的 \(k\) 个数组，每次合并的时间复杂度为 \(O(2^m)\)，其中 \(m\) 是合并的数组的索引。
因此，\(INSERT\) 的最坏情况运行时间是 \(O(n)\)。
使用摊还分析方法，我们给每次插入的操作分配一个 \(lg n\) 的信用，这足以支付其在未来合并中的成本。
所以，每次插入的摊还成本是==\(O(lg n)\)==。
c.
为了实现 \(DELETE\) 操作，首先找到最小的 \(m\) 使得在 \(n\) 的二进制表示中 \(n_m \neq 0\)，这表明数组 \(A_m\) 是非空的。
如果要删除的元素不在 \(A_m\) 中，我们将其从其当前数组中移除，并与 \(A_m\) 中的任意元素交换，然后在 \(A_m\) 中执行删除。
这可以通过在 \(A_k\) 中进行二分查找来实现，时间复杂度为 \(O(\lg n)\)。
然后，将 \(A_m\) 拆分并将元素正确地分配回数组 \(A_0, A_1, \cdots, A_{m-1}\) 中。
因为所有的数组在分配前都是有序的，所以这个过程的时间复杂度主要来自于进行拆分，总共为 \(O(m)\)。
在最坏的情况下，这个时间复杂度是==\(O(\lg n)\)==。
NP完全性证明
最长简单回路问题是在一个图中，找出一个具有最大长度的简单回路（无重复的顶点）。证明：这个问题是 NP 完全的。
解：
- 证明问题属于NP
对于一个给定的解，即图中的一个回路，我们需要验证该回路是否是简单的（没有重复的顶点）并且计算这个回路的长度。
这两个验证步骤都可以在多项式时间内完成。
因此，最长简单回路问题属于NP。
- 证明问题的NP-困难性
从哈密顿回路问题归约，哈密顿回路问题是判定一个图中是否存在一个经过每个顶点恰好一次并返回起点的回路。
归约过程如下：
- 假设我们有一个图 \(G\) 和我们想解决哈密顿回路问题。
- 构建一个新的决策问题：图\(G \(中是否存在一个长度至少为\)n\)（\(n\)是图\(G\)中的顶点数）的简单回路？
- 如果图\(G\)中存在一个哈密顿回路，那么显然存在一个长度为\(n\)的简单回路（即哈密顿回路自身）。
- 反过来，如果图\(G\)中存在一个长度为\(n\)简单回路，由于一个简单回路中的顶点不重复，且长度达到了顶点总数，这个回路必须经过图中的每个顶点恰好一次，因此它也是一个哈密顿回路。
由于哈密顿回路问题是NP完全的，最长简单回路问题也必然是NP困难的。
结论
通过以上的归约，我们展示了最长简单回路问题不仅属于NP，还是NP-困难的。因此，最长简单回路问题是NP完全的。
NP完全性证明与延申（扯到一点点dp）
图\(G=(V,E)\)的独立集是子集\(V'\subseteq V\)，使得\(E\)中的每条边至多与\(V'\)中的一个顶点相关联。独立集问题是要找出\(G\)中具有最大规模的独立集。
a. 给出独立集问题相关的判定问题的形式化描述，并证明它是NP完全的。（提示：根据团问题进行规约）
b. 假设给定一个“黑箱”子程序，用于解决(a)中定义的判定问题。试写出一个算法，以找出最大规模的独立集。所给出的算法的运行时间应该是关于\(|V|\)和\(|E|\)的多项式，其中查询黑箱的工作被看做是一步操作。 尽管独立集判定问题是NP完全的，但在特殊情况下，该问题是多项式时间可解的。
c. 当G中的每个顶点的度数均为2时，请给出一个有效的算法来求解独立集问题。分析该算法的运行时间，并证明算法的正确性。
d. 当G为二分图时，试给出一个有效的算法以求解独立集问题。分析算法的运行时间，并证明算法的正确性。（提示:利用26.3节中的结论。)
a. 形式化描述及NP完全性证明
问题形式化描述： 给定一个图 \(G = (V, E)\) 和一个整数 \(k\)，判定 \(G\) 是否存在一个大小至少为 \(k\) 的独立集 $V' \subseteq V $。
NP完全性证明：
-
证明问题属于NP： 给定一个解，即图中的一个顶点集 $ V' $，我们可以在多项式时间内验证每个边 $ e = (u, v) \in E \(至多与 \(V'\) 中的一个顶点相关联，并且验证\)|V'| \geq k $。
-
证明NP困难性： 可以通过团问题进行归约。团问题是判断图 \(G\) 是否包含大小至少为 \(k\) 的完全子图（团）。考虑图 \(G\) 的补图 $ \overline{G} $，在 $\overline{G} $ 中的独立集与 $G $ 中的团是对应的。如果 \(G\) 中存在大小为 \(k\) 的团，那么在 $\overline{G} $ 中存在大小为 \(k\) 的独立集。团问题已知是NP完全的，所以独立集问题也是NP完全的。
b. 使用黑箱子程序的算法
def find_maximum_independent_set(G, black_box):
n = len(G.vertices)
low, high = 0, n
# 使用二分搜索确定最大的独立集大小
while low < high:
mid = (low + high + 1) // 2
if black_box(G, mid):
low = mid # 存在至少大小为mid的独立集，增大下限
else:
high = mid - 1 # 不存在大小为mid的独立集，减小上限
return black_box.construct_independent_set(G, low)
这个算法的运行时间依赖于黑箱的效率，但通常考虑到二分搜索，其时间复杂性是多项式级别的。
c. 每个顶点度数为2的图的算法
对于每个顶点度数为2的图，图形成一个或多个环。可以用动态规划求解每个环的最大独立集，然后合并这些结果。
def max_independent_set_cycle(cycle):
n = len(cycle)
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 1
# 动态规划数组
dp = [0] * n
dp[0] = 1
dp[1] = max(1, dp[0])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + 1)
# 考虑环的闭合性，最后一个和第一个不能同时选择
return max(dp[n-1], dp[n-2])
算法的时间复杂度为 $O(n) $，其中 \(n\) 是环中的顶点数。
d. 二分图的算法
对于二分图，最大独立集的大小等于顶点数减去最小顶覆盖数。使用最大匹配来计算最小顶覆盖，因为在二分图中，由Kőnig定理可知最大匹配数等于最小顶盖数。
def bipartite_maximum_independent_set(G):
max_matching = bipartite_max_matching(G)
min_vertex_cover = max_matching
max_independent_set_size = len(G.vertices) - min_vertex_cover
return max_independent_set_size
这里的 bipartite_max_matching 函数是用来计算二分图的最大匹配，可能使用Hopcroft-Karp算法，时间复杂度为 \(O(E\sqrt{V})\)。
近似算法优化（集合覆盖）
修改\(APPROX-SUSET-SUM\)过程，使其能够返回\(S\)的一个各元素之和为\(z^*\)的子集
基本思路
- 使用动态规划方法构建一个列表，记录达到不同和的可能性。
- 修改算法，以便在计算过程中跟踪达到每个可能和的子集元素。
修改后的算法步骤
- 初始化：
- 创建一个列表
L，其中L[0]初始化为一个空集（表示和为 0 的子集）。 -
其他值初始化为
None（表示这些和无法通过任何子集达到）。 -
动态规划填表：
-
对于每个元素
x在集合 \(S\) 中：- 从列表
L的最大索引开始向下遍历到x（防止一个元素被重复使用）。 - 对于每个
i，如果L[i]不是None且L[i + x]是None（即i+x还未被更新过），那么设置L[i + x]为L[i]并添加x。
- 从列表
-
寻找最优解：
-
从目标值
t开始，向下查找最接近t但不超过t的索引j，使得L[j]不为None。 -
返回结果：
- 返回
L[j]作为和最接近t但不超过t的子集。
总结来说，这种修改使得算法不仅可以给出一个接近目标和的值，还可以实际返回达到这个和的一个具体子集，增强了算法的实用性。
本站总访问量次