网络基础

IP网络是什么
- IP网络是一个分组交换网络
- 用路由器来转发数据包
- 每个主机都有一个IP地址
IP路由原理：根据目的地址和转发表对每个包（目的地址、源地址和内容为特征）独立的转发判决
网络流：两个通信端点之间的通信流量，不同实体流的粒度不同，流的ID也不同
- 主机间的流<源IP，目的IP>
- TCP流<源IP，目的IP，源端口，目的端口，协议号>
SDN：网络控制API为北向，网络设备控制接口为南向
OpenFlow：定义控制器和交换机间的控制流程和规范的开放控制协议
流表有三个部分组成：
- Match：交换机端口、VLAN ID、源目MAC地址、源目IP地址、源目IP端口、源目L4端口等
- Actions：转发、丢包、发到控制器、操作VLAN tag等
- Counters：数据
SDN控制机制：主动控制（控制器主动下发、请求、删除流表信息），被动控制（控制器收到信息进行响应）

分治

范型（Design Paradigm）：设计算法的通用思路，如分治、贪心、动态规划、蛮力、随机算法、回溯等
分治：将问题拆成具有相同性质的子问题，最终用递归实现
归并算法：将原数组分解为两个子数组再排序，运行时间为 $6n(log_2n+1)$
复杂度分析的原则：只关注最坏情况（任何规模为n的实例的操作时间的上界），忽略常数和低阶项
- A的复杂度比B好，不代表A的耗时总少于B，而是随着实力规模的增加A的耗时增长更慢
$T(n)=O(f(n))$ 代表n大到一定程度后， $T(n)$ 一定小于 $f(n)$ 的常数倍
$T(n)=\Omega(f(n))$ 代表n大到一定程度后， $T(n)$ 一定大于 $f(n)$ 的常数倍
$T(n)=\Theta(f(n))$ 代表n大到一定程度后， $T(n)$ 一定在 $f(n)$ 的两常数倍之间
归并算法复杂度： $O(nlogn)$ ，任何基于比较的排序算法都不可能低于它
- 对于决策树：叶子结点 $l$ 代表排列结果，树高 $h$ 代表比较次数，而 $l\ge A_n^n=n!，l \le 2^h$ ，所以 $h \ge log(n!)=O(nlogn)$
主定理：若 $T(n)=aT(\frac{n}{b})+O(n^d)$ ，则

$T(n)=\begin{cases}& O(n^dlogn),\text{ if } a=b^d \\& O(n^d),\text{ if } a<b^d \\& O(n^{log_ba}),\text{ if } a>b^d\end{cases}$

参数分析：
- a为递归调用次数（一个问题分裂几个子问题），代表子问题数目的增长速率
- b为子规模缩减因子
- d为合并步骤的RT指数因子
- $b^d$ 代表每个子问题RT的缩减速率
- $a=b^d$ 代表每层的RT是一样的
- $a<b^d$ 代表RT逐层减少，根节点的RT占主导
- $a>b^d$ 代表RT逐层增加，叶节点的RT占主导

图基础

连通图：图中任意两个顶点都可达
全连通图：图中任意两个顶点都邻接
关联：与顶点相连的边与该点关联
欧拉圈：一次经过所有边的圈$\Leftrightarrow $顶点度数都为偶数
图的表示方法：
- 邻接链表：每个结点都有一个链表，记录与之邻接的其他节点（推荐，因为多数图算法都需要方便的访问给定顶点的连接点，且占用空间少， $O(n+m)$ ，且很多都是稀疏图）
- 邻接矩阵：n阶方阵，邻接则表示为1，空间为 $O(n^2)$
n个顶点和m条边的关系：
- 无向图： $m\le C_n^2$ ，即 $m=O(n^2)$
- 有向图： $m\le A_n^2$ ，即 $m=O(n^2)$
- 连通图： $m\ge n-1$ ，即 $m=\Omega(n)$
BFS：用队列实现，层的概念， $O(n+m)$
DFS：用堆栈实现，回溯， $O(n+m)$
TWO-PASS算法：给有向图划分强连通分量
- 步骤一：将图反向，运行DFS，获得节点的完成时间（必须回溯时）
- 步骤二：将图反向，从完成时间降序开始运行DFS，记录每条路的leader
- $O(n+m)$
- DFS用堆栈，第一遍的时候直接按完成时间降序放入一个数组

贪心

贪心特点：
- 容易构造算法
- 分析简单
- 正确性很难证明
- 不保证正确
Prim算法：任意顶点扩展，选择权重最小的割边顶点加入树中，直到覆盖所有顶点
- 生成最小生成树（MST）
- 直接实现（每次循环检查所有边），复杂度为 $O(mn)$
- 用堆（完全二叉树，可用数组实现）实现，加入对象为 $O(\log n)$ （放到最后再冒泡），取出最小key值为 $O(\log n)$ （删除根，将叶子放到根处向下沉），建堆为 $O(n)$ ，删除元素为 $O(\log n)$ ，该算法复杂度为 $O(m\log n)$
Kruskal：按权重升序排序，从小纳入边直到成环前
- 直接实现，调用BFS，复杂度为 $O(mn)$
- 用UNION-FIND，维护leader、size属性，成环检测用FIND操作 $O(m)$ ，合并用UNION操作 $O(n\log n)$ ，算法复杂度为 $O(m\log m)$
Dijkstra算法：维护权重（距离源点的距离）和前继结点，逐步更新权重，并纳入距离最近的点，直到覆盖所有顶点
- 直接实现，每次循环检查所有边，复杂度为 $O(n^2)$
- 用堆实现，复杂度为 $m\log n$
- 用桶实现，桶数量为nC+1，C为权重最大值，找第一个非空桶 $O(nC)$ ，合并桶 $O(m)$ ，复杂度为 $O(m+nC)$
- 用循环桶实现，只需用C+1个桶，顶点的桶编号为顶点权重%(C+1)，复杂度为 $O(m+nC)$
- 减少桶的数量，可以每个桶覆盖一定范围的距离标记，桶内用堆实现
单源单宿问题：双向Dijkstra算法
给宿点求源点：
- 方法一：对边反向，重新调用正向Dijkstra算法
- 方法二：更新时，只检查入度边

动态规划

动态规划：带表的分治，子问题的解储存在一个表中以供后续使用
- 把最佳解看成一系列决策的结果
- 假如知道最后一次的决策结果，剩下的解可能是某个子问题的最佳解
- 对最后一次决策进行蛮力搜索
最佳子结构：最佳解的特征
最大加权独立集问题（MWIS）：图的边上无权重，顶点有权重，求独立集（两两不邻接）使权重最大
Bellman-Ford算法：每次遍历所有边，发现不满足最优性条件则更新，若n次循环还有更新则有负圈
- 直接实现，复杂度为 $O(nm)$
- 用X-Queue实现，前后都可以插入元素，但只能从前面取元素，复杂度为 $O(nmC)$
任意顶点对的最短路（APSP）：给定有向加权图给出任意顶点的最短路或检测出负圈
Floyd-Warshall算法：复杂度为 $O(n^3)$
Johnson算法：增加顶点和n条边调用BF，权重变换得到新图并调用n次Dijkstra
- 复杂度为 $O(nmlogn)$

最大流问题

最大流问题：给定有权有向图寻找从起点到终点的最大流量
Ford-Furkerson算法：建立剩余网络，循环找简单路经，且增加最少流量的反向路径
- 复杂度为 $O(mf)$ ， $f$ 为最大流大小（可能每次循环都增加1）
最大流等于最小割
Edmonds-Karp算法：找增广路径时，使权重为1找最小跳数路径（BFS），其余与FF算法一样
- 分层图，去掉同层、高层指向低层的边
- 复杂度为 $O(m^2n)$
Dinic算法：在分层图上算阻塞流
- 复杂度为 $O(mn^2)$

附录

三种范型比较