这里主要记录不太清晰的、一下子反应不过来的、怕忘记掉的、觉得有趣想记下来的东西

1 算法基础

内容就是最基础的计算复杂度

$$
定义:存在n_0和c,使得n>n_0时,f(n)?cg(n)\\
O:上界\\
o:不是”上确界”的上界\\
\Omega:下界\\
\omega:不是”下确界”的下界\\
\Theta:同阶
$$
一些公式：
$$
\log(n!)=\Theta(n\lg n)\\
n!=\sqrt{2\pi n}(\frac n e)^n(1+\Theta(\frac 1 n))\approx\sqrt{2\pi n}(\frac n e)^n
$$

下面那个叫斯特林公式

摊还分析

聚合分析：一个操作序列中n个操作的最坏情况复杂度，然后平均掉。类似双指针

2 算法分析数学方法

递归树

利用递归树猜测，然后需要利用数学归纳法证明正确性。

主定理

对于这样形式的递归复杂度求解：
$$
T(n)=aT(\frac n b )+f(n)
$$
其中$a$，$b$为常量，$a\ge 1$，$b>1$，$a$表示子问题个数，$b$表示子问题规模

那么
$$
T(n)=\cases
{
\Theta(n^{\log_b a}):\text{若存在常数}\epsilon>0，有f(n)=O(n^{\log_b{a-\epsilon}})\\
\Theta(n^{\log_b a}\lg n):若f(n)=\Theta(n^{\log_b a})\\
\Theta(f(n)):若存在常数\epsilon>0，有f(n)=\Omega(n^{\log_b a+\epsilon})，且对某个常数c<1和所有足够大的n，有af(\frac n b)\le cf(n)
}
$$
感受：$f(n)$主导就$f(n)$，递归主导就递归，相同就加个$\log$

注意：某些情况不能直接使用主定理

例：
$$
T(n)=2T(\frac n 2)+n\lg n\\
这里f(n)不符合第三类的条件，因为不存在这样的\epsilon\\
但这个问题可以利用递归树求解，答案为O(n\lg^2 n)
$$

主定理的扩展

为了解决上面这个不能用主定理的问题，可以对第二类情况作扩展（原式即扩展式中$k=0$时的情况）：
$$
若存在k\ge 0,f(n)=\Theta(n^{\log_b a}(\log_2 n)^k)\\
则T(n)=\Theta(n^{\log_b a}(\lg n)^{k+1})
$$

3 分治策略

大整数乘法

$$
x\times y=2^nx_Ly_L+2^{\frac n 2}(x_Ly_R+x_Ry_L)+x_Ry_R\\
\because x_Ly_R+x_Ry_L=(x_L+x_R)(y_L+y_R)-x_Ly_L-x_Ry_R\\
\therefore 减掉的两项都在上面算过了，总共只需要计算三次乘法\\
\therefore T(n)=3T(\frac n 2)+\Theta(n)\\
根据主定理，总复杂度\Theta(n^{\lg _2 3})
$$

Strassen算法

矩阵乘法的朴素分治时间复杂度没有提升（两个矩阵各自分成四个小矩阵，共八次对小矩阵的乘法），但应用类似上面大整数乘法的方法，发现只需要计算七次乘法后加加减减即可计算出答案。故复杂度可以降低为$\Theta(n^{\lg_2 7})$

4 线性时间的选择

nth_element算法的最坏复杂度仍然是$\Theta (n^2)$的，但是可以优化使得最坏复杂度为$\Theta(n)$

如何优化？使选取的主元必定大于$\frac 1 x$的元素即可。根据主定理可以得到最坏复杂度变为线性了。

如何选取？考虑将每$x$个数分成一组，每组找出一个中位数，再对这些中位数找中位数（递归）即可。

5 线性时间的排序

比较排序算法的下界：利用决策树说明

6 动态规划

子问题的依赖关系需要是一个DAG

最优子结构性质：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。即：问题的最优解包含着其子问题的最优解。

PPT中提到的重叠子问题概念：某几个问题依赖同一个子问题的答案，那只需要算一次记下来就好了

似乎对证明的要求不高，掌握方法即可

7 贪心算法

最优子结构性质

贪心选择性质：与dp的区别。可以通过一系列局部最优的选择来求出全局最优解。

需要证明。但似乎证明也不会仔细考

8 贪心算法的应用

最短路-Dijkstra

最短路-Bellman-Ford

差分约束

最短路-Floyd

传递闭包

稀疏图的Johnson算法

用来算稀疏图的多源最短路。首先处理负权边：对每个点赋点权f并调整边权，使得从u到v的边的长度为f(u)-f(v)+l’(u,v)。如何做到？建立一个超级源点向每个点指一条边权为0的边，跑bellman-ford即可（此时可以检测是否存在负环）。然后从每个点出发跑一遍dijkstra（跑的时候只需要考虑边权，因为答案=f(u)-f(v)+shortest_path(u,v)，与其它结点的f无关）。

复杂度$O(VE\lg V)$，若斐波那契堆则$O(VE+V^2\lg V)$

最小生成树

证明方向：反证法，考虑若删掉方案中一条边的话，生成树不可能更优。

9 线性规划

$$
设z是需要最大化的答案，C是系数，X是变量的取值，b是常数\\
max~z=CX\\
AX=b\\
X\ge 0
$$

在编程的时候，采用“单纯形表”的方式存储

以下面的式子为例
$$
\max x_1+14x_2+6x_3\\
s.t\cases{
x_1+x_2+x_3+x_4=4\\
x_1+x_5=2\\
x_3+x_6=3\\
3x_2+x_3+x_7=6\\
x_1,x_2,x_3,x_4,x_5,x_6,x_7\ge 0
}
$$

x1 x2 x3 x4* x5* x6* x7* b
c1=1 c2=14 c3=6 c4=0 c5=0 c6=0 c7=0 -z=0
1 1 1 1 0 0 0 4
1 0 0 0 1 0 0 2
0 0 1 0 0 1 0 3
0 3 1 0 0 0 1 6

非基本变量是参与答案运算的。基本变量（上面打了*）是拿来做基底的。

表中就是直接可以看出来的一个基本可行解。但有时候直接把非基本变量取0并不能得到可行解。

可以引入一个辅助线性规划：新引入$x_0$变量，要求最大化$-x_0$（因此只有$x_0$一个基本变量）。如果$x_0$不能搞成0的话那显然无解。如果搞成了那显然就有一组基本可行解了。

对偶原理

$$
\max c^T x:Ax\le b,x\ge0\\
\min b^T y:A^Ty\ge c,t\ge 0
$$

二者对偶，最优值相等或都不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//by Richard
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
using namespace std;
mt19937 rnd(19260817);
const int inf=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> pii;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
using namespace std;
const int maxn=11111,maxm=11111;
const double eps=1e-8;
double a[maxm][maxn], basicans[maxn];
int n,m,id[maxn*2]; //记录最后的方程左边, 是原来的哪个变量
void pivot(int l,int e,int n,int m)
{
    //e是一个非基本变量，l是一个基本变量，分别称作entering variable和leaving variable
    swap(id[n+l],id[e]);//交换
    double x=a[l][e];
    a[l][e]=1;
    rep(i,1,n) a[l][i]/=x;
    rep(i,0,m)
    {
        if (i==l||abs(a[l][e])<eps) continue;//确保a[l][e]!=0
        double t=a[i][e];
        a[i][e]=0;
        rep(j,0,n) a[i][j]-=t*a[l][j];
    }
}
bool simplex(int n,int m)
{
    while (1)
    {
        int l=-n,e=0;
        //找到第一个（为了符合blend规则，避免循环）系数大于0的非基本变量，要把它处理掉。entering
        rep(i,1,n) if (a[0][i]>eps&&id[i]<id[e]) e=i;
        //系数都小于0，即当前是最优了
        if (!e) break;
        //找到范围最紧的基本变量，要把它变成非基本变量。leaving
        double minn=1e18;
        rep(i,1,m)
        {
            if (a[i][e]>eps)
            {
                double x=a[i][0]/a[i][e];
                //最小比值原则
                if (x<minn||(abs(x-minn)<eps&&id[n+i]<id[n+l])) minn=x,l=i;
            }
        }
        //如果无界，可以取值无穷大，那就无解了
        if (l==-n) return false;
        pivot(l,e,n,m);
    }
    return true;
}
bool init_simplex(int n,int m)//找基本可行解
{
    while (1)
    {
        int e=0,l=-n;
        //如果存在负值就要处理，因为可行解要求变量都要非负
        rep(i,1,m) if (a[i][0]<-eps&&id[n+i]<id[n+l]) l=i;
        if (l==-n) break;//不存在非负的，那当前解已经可行了
        rep(j,1,n) if (a[l][j]<-eps&&id[j]<id[e]) e=j;
        if (!e) return false;//没人能跟负的调整，无法解决负值问题，所以无解
        pivot(l,e,n,m);
    }
    return true;
}
int solve(int n,int m)
{
    rep(i,1,n+m) id[i]=i;
    id[0]=inf;
    if (!init_simplex(n,m)) return -1;//不存在基本可行解
    else return simplex(n,m);
}
int main()
{
    //由于这题要求的是最小值，所以需要应用对偶原理调整，c和b换了位置，a也转置了
    cin>>n>>m;//n天（n个不等式约束），m种志愿者（m个初始变量）
    rep(i,1,n) cin>>a[0][i];//是上面的系数数组
    rep(i,1,m)
    {
        int s,t,c;
        cin>>s>>t>>c;
        rep(j,s,t) a[i][j]=1;//第i种志愿者在第j天有用
        a[i][0]=c;//就是上面例子中的b数组，放在了a[x][0]
    }
    solve(n,m);
    printf("%lld\n",(LL)(-a[0][0]+0.5));
    return 0;
}

10 网络流

流网络的定义

不存在反向边

源节点外每个点入度都不为0

满足两个性质：容量限制，能量守恒（每个点流出=流入）

流的规模|f|为s的净流出或t的净流入

显然网络流是一类线性规划问题，可以利用单纯形求解。而单纯形的过程就是走增广路的过程。

割

切割：把结点集合划分成S和T两部分，使得源点s属于S，汇点t属于T,则通过切割的S到T的净流量等于当前流的流量。（意思就是说这个切割方案把流完全切断了）

最大流最小割定理：下列条件等价：

  1. f是G的一个最大流
  2. 残存网络G_f不包括任何增广路径
  3. |f|=c(S,T)，其中(S,T)是流网络G的任意一个切割

证明要求的其中一个推论：不管怎么流，任意一个切割总是能把它全切了，所以最大流小于最小割。

Ford-Fulkerson

暴力找残余网络中的增广路，直到找不到

复杂度$O(E\cdot |f|)$

Edmonds-Karp

BFS找增广路，保证按顺序从近往远找，省去很多流过去又反悔的时间

复杂度$O(VE^2)$

Dinic

在Edmonds-Karp的基础上引入分层图的方法，每一次BFS可以走多条增广路

复杂度$O(V^2E)$

匈牙利算法

二分图匹配问题中的特殊版走增广路

11 斐波那契堆

常规操作中只有pop（Extract-Min）是lg的，其它的均摊复杂度都是O(1)

大致就是维护lgn个小堆，堆顶之间用链表连起来。小堆的大小根据斐波那契数列有下限（上限就是正常堆的上限），且相同大小的小堆需要合并成大一点的小堆。利用一系列神仙般的操作（不至于考这个吧）维护就能搞出来了。

对于删除操作，斐波那契堆使用decrease_key后extract_min，所以复杂度是extract_min的复杂度lg

在学习斐波那契堆之前课上讲到了二项堆，因为有些思路是相通的。也是小堆合成大堆。和斐波那契堆的性能就差在decrease_key上。

12 NP完全性

P：多项式时间可解

NP：已有一组解的情况下多项式时间可验证（所以P问题一定属于NP问题）

NPC：最难的一类NP问题，多项式时间是否可解未被证明

NP-Hard：比NPC难解的或一样难解的问题

13 近似算法

概念

近似比：
$$
r_A(I)=\frac{A(I)}{OPT(I)}\ 若是最小化问题\\
r_A(I)=\frac{OPT(I)}{A(I)}\ 若是最大化问题
$$
算法$A$的近似比为$r$，则称$A$~是$r$-近似算法。

假设$P\not=NP$，NPC的组合优化问题按可近似性分成3类：

  1. 完全可近似：对任意小的$\varepsilon$，存在$(1+\varepsilon)$-近似算法，例如背包问题

  2. 可近似：有常数近似比的近似算法，例如最小顶点覆盖问题、多机调度问题

  3. 不可近似：不存在常数近似比的近似算法，例如旅行商问题

最小顶点覆盖问题

选中一些点，使得所有边都有端点被选中

按度数从大到小选择的贪心，近似比是$\lg$的

MVC算法

随便选一条边，把边上两个端点选中，并把端点相关的边全删光。显然是个2-近似算法

选中的边的条数必定是答案的一个下界。（也很显然）

所以就有了下界x和上界2x

多机调度问题

单机是贪心

G-MPS

多机用贪心算法G-MPS，近似比？

推论1：$OPT(I)\ge \max_{a\in A} t(a)$，机器的最大负载不小于单个作业的加工时间

推论2：$OPT(I)\ge \frac 1 m\sum _ {a\in A}t(a)$，机器的最大负载不小于所有机器的平均负载

假设所有作业加工完成后，第j台机器的负载最大。那么在分配最后一个任务之前它的负载最小。
$$
t_总\le \frac 1 m (\sum _ {a\in A} t(a)-t(b))+t(b)
$$
继续简单推一推就能发现这个贪心是2-近似算法，当很多短任务和一个长任务时取到极值

改进G-MPS

加工时间由大到小排序，再贪心分配

利用上面类似的方法，可以证明这个算法是1.5-近似的

旅行商问题-满足三角形不等式的特例

点都在平面上，没有道路限制，点与点都可以直接到达

最邻近算法NN

每次都走最近的没去过的城市。近似比是$\lg$的。没有价值

最小生成树启发式近似算法

$$
TSP代价\ge TSP删除任意一条边的代价\ge MST代价
$$

由MST可以得到一条欧拉回路，按欧拉回路的访问顺序可以得到一条哈密顿回路。

这个方法是2-近似算法，因为
$$
假设H^ *是最优路线，H^ *对应的生成树为T^ *，最小生成树是T，对应的欧拉回路是S \\
W(S)=2W(T)\le 2W(T^ *)<2W(H^ *)=2OPT(I)
$$

最小权匹配近似算法MM

最小生成树T上度数为奇数的顶点集X。根据握手定理这里有偶数个顶点。求出顶点集在原图上导出的子图G’（包含X和所有X内连接的边），求G’的最小权完全匹配M，使得M中的边连接了G’的全部顶点。将M和T的边集合并，得到欧拉图。在欧拉图上寻找一个欧拉回路，抄近路得到哈密顿回路。

该方法是3/2-近似的。证明相对比较复杂。

原版旅行商问题

如果$P\not=NP$，则对任何常数$\rho\ge1$，旅行商问题不存在具有近似比为$\rho$的多项式时间近似算法。即该问题不可近似。

证明：如果有这样的方法，那拿它找哈密顿回路，就可以解决哈密顿回路问题了。那就$P=NP$了

01背包

常规dp的时间复杂度与价值的取值有关。如果实数域就直接gg

贪心算法G-KK

按价值重量比贪心，贪完最后一步把能换的换成价值大的

证明：

设l是按价值重量比排序的第一件没装入的物品，则
$$
OPT(I)<\text{G-KK}(I)+v_l\\
\le \text{G-KK}(I)+v_{max}\\
\le \text{2G-KK}(I)
$$

PTAS算法

  1. 令$m=\lfloor \frac 1 \epsilon \rfloor$

  2. 按价值重量比排序

  3. t从1尝试到m，每次尝试都从前m个物品里取t个加入背包，再对未装入的物品使用G-KK算法

  4. 从m次尝试中找到最优的

总运行次数用组合数可以计算出来，是多项式的，$O(n^{\frac 1 \epsilon}+2)$

算法是$1+\epsilon$-近似的，证明也比较简便