algorithm compressive

概述

1. 二分法最好情形比较 $1$ 次，最坏 $\lfloor \log n \rfloor +1$
2. 合并排序的比较次数 $min(n_1,n_2) \sim n_1+n_2-1$
3. 选择排序比较次数恒为 $\frac{n(n-1)}{2}$
4. 插入排序比较次数 $n-1 \sim \frac{n(n-1)}{2}$
5. 自底向上合并排序：第 $k$ 次迭代中，对 $n/2^k$ 个有$2^k$ 个元素的数组一共进行了 $n/2^{k+1}$ 合并，总比较次数为 $2^k \sim 2^{k+1}-1$，比较次数为 $\frac{n \log n}{2} \sim n \log n -n + 1$
6. 根据评分的歌曲随机播放算法：1：根据评分复制编号次数（时间复杂度$O(1)$，空间复杂$O(n*歌曲评分)$）；2：根据评分生成区间+随机数判断落入哪一个区间（时间复杂度$O(logn)$，空间复杂度$O(n^2)$）
7. euclid 算法最坏情况当$m,n$为 fibonacci 数列中连续的数，$O(\log n)$

数学知识

1. 相对补 $A \bigoplus B=(A-B) \bigcup (B-A)=(A \bigcup B)-(A \bigcap B)$
2. 集合的二元关系：空集；非空集合且元素都是有序对
3. 等价关系=自反+对称+传递；偏序关系=自反+反对称+传递；可比关系？

数据结构

1. 堆不一定是完全二叉树（如斐波那契堆）
2. 堆的基本操作：make(每一个非叶子节点下移，时间复杂度 O(n))、insert(插堆尾+siftUp)、delete(与堆尾元素交换，尾大则siftUp，尾小则siftDown)、pop
3. 计数排序（适用于整数且数值较小）：A(待排序)、B(已排序)、C(临时空间,长度为 A 的最大值)，C[i] 表示 A 中值为 i 的元素所在的区间左端点，也即 i 在 B 中的下标
4. 基数排序（适用于具有相同或相近位数的排序）：对所有数从低位到高位依次进行排序（位数不齐补0）（必须使用稳定排序算法、也可以用表的方法）
5. 不相交集基本操作：find、union（rank、权重平衡）
6. 路径压缩：找 y 的根节点，找到之后重复操作并将途径所有节点直接指向根节点（即成为根节点的儿子节点）；可能会造成根节点的 rank 大于树的高度（find 操作不会改变 rank）

递归

1. 解决递归的相关问题最重要的两个要素是边界条件和递归方程

2. perm 算法关键在于 交换+递归+交换，时间复杂度 $O(nn!)$

3. 整数划分：$q(n,m)$ 表示正整数 $n$ 的最大加数不超过 $m$ 的划分，则有 ：$q(n,1)=1；q(n,m)=q(n,n)[m>n]；q(n,n)=q(n,n-1)+1；q(n,m)=q(n, m-1)+q(n-m,m)$

   (最后一个式子表示不大于 $m$ 的划分由至少包含一个 $m$ 以及不大于 $m-1$ 构成)

4. 递归树：节点的总和为时间复杂度

5. $f(n)=f(\lfloor c_1n \rfloor)+f(\lfloor c_2n \rfloor)+bn$；当 $c_1+c_2=1,O(n \log n) $ ；$c_1 + c_2 < 1, \Theta(n)$

6. $T(n)=aT(n / b) + n^x$；当 $a < b^x, \Theta(n^x)$ ；$a=b^x, \Theta(n^x \log n)$；$a > b^x, \Theta(n^{log_b a})$

7. 桶排序(桶之间顺序已经确定，只需要桶内排序)：$n$ 个数放到 $k$ 个桶，平均 $n+\frac{n^2}{k}$

分治

1. 过程：分解+解决+合并

2. 找出$A$中第$k$小的元素：(1)五个元素一组，组内排序(2)取出每个组中间的元素形成组$B$，递归找$B$的中间的元素$m$(3)用$A_1,A_2,A_3$分别存储$A$中小于、等于、大于$m$的元素，若$k<=len(A_1)$，在$A_1$中递归寻找；若$k<=len(A_1)+len(A_2)$，返回$m$；否则在$A_3$中递归寻找

3. 快速排序：找到指定元素所在位置，分割左、右子数组。

4. 大整数乘法：$XY=(A·2^{n/2}+B)(C·2^{n/2}+D)=A·C·2^n+((A+B)(C+D)-AC-BD)·2^{n/2}+BD$

   时间复杂度 $O(n^{log_23})$

5. 最大子数组(分治法)：$max(左半边，右半边，跨中间)$ 跨中间的求法为：遍历直到两边（先遍历完左边或者右边都可以）并记录和最大的两个下标。时间复杂度 $O(n \log n)$

动态规划

1. 动态规划的实质是分治和消除冗余，基本步骤为：找出最优解性质；递归定义最优值；自底向上算出最优值；根据最优值构造最优解
2. 矩阵连乘问题：设$A_i=p_{i-1} \times p_{i}$；$A[i:j]$表示$A_i·…·A_j$；$m[i:j]$表示$A[i:j]$最优值；$s[i:j]$记录$A[i:j]$最优划分的位置(即$k$)。则有$m[i,i]=0;m[i,j]=min(m[i,k]+m[k+1,j]+p_{i-1} \times p_k \times p_j)$
3. 求$X,Y$最长公共子序列：$c[i:j]$表示$X$的前$i$个元素和$Y$的前$j$个元素得到的最长公共子序列的长度，则$c[0:k]=c[t:0]=0$；$c[i:j]=c[i-1:j-1]+1$ $ if \,\,X[i]=Y[j]$；$c[i:j]=max(c[i-1:j],c[i:j-1])$ $if \,\, X[i]!=Y[j]$。最长的公共子序列为$c$中的拐点对应的元素
4. 求$a[1:n]$最大子数组(DP)：$b[j]$表示$a[1:j]$中包含$a[j]$的最大子数组的值，当$b[i-1]>0$时，有$b[i]=b[i-1]+a[i]$；当$b[i-1]<0$时，$b[i]=a[i]$。最大子数组为从最大的$b[k]$到左边最后一个非负的$b[t]$
5. 动态规划必须具备最优子结构和子问题重叠
6. 0-1背包问题：$m[i:j]$表示在容量为$j$和前$i$个物品的情况下的最优值，当$0<j<w_i$时，有$m[i:j]=m[i-1:j]$；否则$m[i:j]=max(m[i-1:j],m[i-1:j-w_i]+v_i)$。选用的背包可以通过$m[i:j],m[i-1:j]$的关系来确定
7. floyd：$d^k[i:j]$表示经过前$k$个后$i,j$之间的最短距离，则$k=0$时$d^k[i:j]=初始距离$$d^k[i:j]=min(d^{k-1}[i:j],d^{k-1}[i:k]+d^{k-1}[k:j])$ 第$k$次迭代中$k$行$k$列都不变
8. OBST：$k[1:n]$是已排序关键字序列，$d[0:n]$是伪关键字序列，且有$d_{i-1}<k_i<d_i$，$p[1:n]$为关键字搜索频率，$q[0:n]$为伪关键字搜索频率，且 $\sum p_i+\sum q_j=1$ ，$e[i:j]$为包含$k[i:j]$和$d[i-1:j]$的最优值，$w[i:j]$为 $\sum_{k=i}^j p_k+\sum_{t=i-1}^j q_t$，$root[i:j]$记录形成$e[i:j]$的根节点。则有$e[i,i-1]=q_i$；$e[i:j]=min(e[i:k-1]+e[k+1:j]+w[i:j])$ 这里的$k-1$从$i-1$开始，$k+1$可到$j+1$
9. 金钱分配问题(n 种面值硬币兑换 y 元)：$M[k]$表示$k$元的最优解，则$M[k]=min(M[k-v_i]+1)$

贪心算法

1. 贪心算法的证明：将贪心解与任一最优解比较，如果不同，寻找第一个不同的$X_i$，证明用贪心解替换最优解之后总价值不减，反复进行下去即可得贪心解即是最优解
2. 活动安排问题(greedy)：按照结束时间排序；选择最早开始的活动；删除在该活动结束之前就开始的活动；重复上述过程。（证明：用子问题中最早结束的活动替换子问题的最大兼容活动子集中最早结束的活动）
3. 霍夫曼编码(左零右一、左小右大)：算法实现可以用小根堆(每次弹出两个合并在放回堆)。正确性的证明(最低频的一定深度最深+最优子结构?)
4. 最小生成树：包含图的所有顶点且边权之和最小的树
5. 最小生成树性质：将顶点划分为两个集合$U,V$，则$U,V$中权值最小的边一定在图的某个最小生成树中
6. Prim：将顶点划分为两个集合$U,V$，初始$U=\phi$。将根节点加入，作为当前节点并更新所有与其相邻的节点；加入权值最短的边对应的顶点并作为当前顶点；重复上述步骤直到加入所有的顶点。证明?。时间复杂度$O(E \log V)$
7. Kruskal：在边所对应的两个点的祖先节点不同时依次将权值最小的边加入。可以用并查集和小根堆实现。时间复杂度$O(E \log E)$
8. Dijkstra：用$\lambda[1:n]$表示和源点的最短距离，将顶点划分为两个集合$X,Y$，初始$Y = 源节点$，将$X$中与源节点距离最短(即最小的 \lambda[k] 对应)的点$y$加入$X$(这也是和Prim不同的地方)；更新所有与$y$相邻的节点的$\lambda[k]$值
9. dijkstra证明(数学归纳法)：$\lambda[1:n],\xi[1:n]$为算法求得最短路径和实际最短路径。对新加入的点$y$，在其真实最短路径经过的点中找到逆向找到第一个$X$中的点$x$。则若$x,y$中没有其他点，有$\lambda[y] \le \lambda[x]+dis[x:y]$(将$X$加入时算法的更新操作)$=\xi[x]+dis[x:y]=\xi[y]$；若$x,y$中有点$w$，则$\lambda[y] \le \lambda[w]+dis[x:w]=\xi[w] $$\le xi[y]$
10. B-F：$d[1:n]$为距离数组。遍历图中的每一条边并作松弛(边 <u,v>，如果 d[v]>d[u]+dis[u:v]，则 d[v]=d[u]+dis[u:v] )，遍历$i$次时，即找到经过$i$条边的最短距离(并不一定是最终的最短距离)，至多遍历$n-1$次即可找出源点到其他点的最短距离；遍历第$n$次时，若存在$k$使得$d[k]$发生改变，说明存在负环。
11. B-F改进(spfa)：B-F算法中只需要对新加入的节点进行松弛，可以用队列实现这个结构。(某个点入队超过 n 次表明存在负环)

图

1. 先序号：先序遍历的序号。后序号：回溯的序号。无向图：对于某条边$(u,v)$，若$vis[v]=0$，则为树边；否则为回边。有向图：对于某条边$<u,v>$，若$vis[v]=0$，则为树边；否则若$u$是$v$的祖先，则为前向边；否则若$v$是$u$的祖先，则为回边；否则为横跨边
2. 图回路判定：若是联通的无向图，仅当$|E|=|V|-1$，否则可根据是否有回边来判断
3. 拓扑排序(有向无回路)：从入度为$0$的点(有多个时可以新增一个节点指向这些入度为$0$的节点)进行DFS，反序号从大到小对应一个拓扑序
4. 寻找关节点(无向图中存在某两个点之间的所有路径必须经过该节点)：每个点$v$有两个信息$\alpha_v=先序号,\beta_v=min(\alpha_v,\alpha_{parents},\beta_{sons})$，若点$v$有回边，则$\alpha_{parents}$为祖先节点的$\alpha$，$\beta_{sons}$指孩子节点的$\beta$。判断：若是$v$根节点，则至少有两个儿子；若不是根节点，则$v$至少有一个儿子$w$满足$\beta_w \ge \alpha_v$
5. 强连通分支(任意两个点之间都有路径的有向图)：进行深度优先搜索得到每一个点的后序号；颠倒图中边的方向；从后序号最大的点开始，在新图中进行DFS；形成的每一棵树即为一个强连通分支
6. BFS有向图中只有树边和横跨边；无向图中只有：树边和回边和横跨边
7. DFS有向图中边分类：DFS获得先序号$pre$和后序号$post$，对于边$<x,y>$，若$vis[y]=0$，则为树边；否则若 $x_{pre}<y_{pre} \quad and \quad x_{post}>y_{post}$ ，则为前向边；否则若 $x_{pre} > y_{pre} \quad and \quad x_{post}<y_{post}$ ，则为回边；否则为横跨边

回溯

1. 回溯框架：若已有部分解$(x_1,…,x_j)$，考察$v=(x_1,…,x_{j+1})$：若是最终解，则输出或结束；若是部分解，则选择$X_{j+2}$中的最小元素$x_{j+2}$；否则若$X_{j+1}$中还有没有用过的元素，则选择该元素作为$x_{j+1}$，若无其他元素，则回溯，将$X_j$中下一个元素作为$x_j$，重置$X_{j+1}$

k = 1 # 层数
while k > 0:
    if unchecked(X[k]) and boundry(X[1],...,X[k]): # boundry为约束函数, unchecked 返回所有可能的值
        if is_answer(X[1],...,X[k]):
            print(X[1],...,X[k])
        if k < n:
            k = k + 1
        else:
            reset(X[k])
            k = k - 1

2. 0-1背包问题：$P34$在哪里减？改进方法为左子树用边界条件右子树用约束函数(小数背包问题)进行剪枝
3. 最大团问题(找最大完全子图)：左子树用可行性条件，右子树用当前最优值剪枝
4. 单源最短路径(分支限界法)：经过某节点到终点的下界(不大于最优解的界限)为：源点到该节点的最短路径+此节点的最短边(点是可以重复取的。若已经到终点：不大于对顶元素时找到解，否则继续入堆
5. 分支限界法找到的上界(下界)必须总是保证不少于(不大于)最优解(即比最优解还要优，虽然不一定存在)，才能保证最后获得正确的结果
6. 0-1背包问题：用小数背包的结果作为上界，可用当前最优解和上界相比进行剪枝
7. TSP：可先用贪心算法找到一个解(不一定是最优解)进行剪枝。用每个点的相邻最近的两个顶点的距离(若已经有选择的边则必须算上选择的边)之和相加除以二取上整作为下界
8. 任务分配问题：贪心+最优时间(不管任务是否已经分配)作为下界

NP

1. $P$类问题：对于一个判定问题，能够以$O(n^k)$运行一个确定性算法(每一步只有一个确定的选择)得到答案。$NP$类问题：对于一个判定问题，能够以$O(n^k)$时间运行一个非确定性算法(猜测+验证)得到答案。简单来说，$P$可以在多项式时间内解出，$NP$能够在多项式时间验证解(显然 P \subseteq NP )。 NP 完全问题： NP 类问题+每一个$NP$类问题都可以在多项式时间规约为该问题。$NP$难问题：所有$NP$类问题能在多项式时间化为该问题，但该问题不一定是$NP$类问题。NPI 问题：不知道属于 P 还是 NP 。
2. 证明一个问题是$NPC$问题：$NP$问题+一个已知的$NPC$问题能在多项式时间转化为该问题