时间复杂度
基本原则
常数优化
- IO优化(快速读写)
- 避免浮点数, 尽量只处理整数
- 快速乘法, 通过对乘数拆解做移位
- 避免除法, 2的整数次幂除法可以用移位代替
- 避免取模, 快速取模方法
基本思想
递归
主要可以分为如下三种:
- 尾部递归, 就是循环, 不支持循环的语言会有尾递归优化
- 中间递归, 可以用一个栈模拟栈帧来将其转为循环, 比如阶乘的递归实现
- 树状递归, 这个就比较复杂了, 最好是从需求上将其转为循环, 比如斐波拉契数列的递归实现
分治
前提: 如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解, 并可利用这些子问题的解求出原问题的解
流程:
- 分解: 将一个问题分成多个类似的子问题(中间递归或者树状递归都可以)
- 解决: 简单子问题可以直接求解
- 合并: 将子问题的解合并成原问题的解
状态和状态转移方程:
- 状态: 你要求解的子问题
- 状态转移方程: 如何将子问题合并
例子:
- 二分查找
- 快速排序
- 归并排序
- MapReduce
贪心
前提:
- 局部最优解可以合成为全局最优解
- 某个状态以前的过程不会影响以后的状态, 只与当前状态有关(无后效性)
流程:
- 分解: 将一个问题分解成线性的多个子问题(中间递归)
- 解决: 对每一个线性子问题求局部最优解
- 合并: 将子问题的局部最优解合并成全局最优解
可以视作为分治的一种特殊情况, 问题可以被分解链式的单个问题, 最后合并的时候是线性合并
动态规划
前提: 将原问题分解成为子问题后, 存在重叠子问题
可以视作为分治的一种特殊情况, 同样要求问题可以被分解为链式的单个问题, 只不过由于分解之后的子问题可能重复, 所以保存每一个子问题的最优解, 这个最优解可能在不同的状态下会被更新.
通常容易用递推实现
离散化
只考虑需要的值, 而不用考虑整个值域
基本数据结构
- 逻辑结构: 集合/线性结构/树形结构/图形结构
- 存储结构: 顺序存储/链式存储/索引存储/Hash存储
线性表
- 数组/链表
- 队列/栈
树
图论
存储方式
- 邻接表
- 邻接矩阵
基础算法
搜索和遍历
- BFS
- DFS
最短路算法
松弛操作: 更新两点距离
Dijkstra
- 单源最短路
- 要求: 非负权边
- 适合稠密图, 邻接表
思路: 贪心 O(N^2)
- 分为已处理集合P和未处理集合Q
- 每一步从Q中选择距离源点s最近的点u, 更新源点s到点u所有近邻的距离
SPFA(Bellman-Ford)
- 稀疏图/负权边
思路: 基于BFS O(kN)
- 源点s入队列
- 出队列节点u, 如果可以松弛, 节点u的所有近邻入队列
Floyd
- 多源最短路
思路: 动态规划
假设>$D_k(i, j)$<表示从i到j的最短路径, 且只经过>$[1, k]$<的节点
- 若经过k点, 那么>$D_k(i, j) = D_{k-1}(i, k) + D_{k-1}(k, j)$<
- 若不经过k点, 那么>$D_k(i, j) = D_{k-1}(i, j)$<
- 因此: >$D_k(i, j) = \min{D_{k-1}(i, j), D_{k-1}(i, k) + D_{k-1}(k, j)}$<
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);最小生成树
Prim
思路: 贪心 O(N^2)
- 往集合V加入起始点s
- 找到一端在V中另一端不在V中且权值最小的边
- 记录这条边, 并把节点添加到V中
- 直到所有节点都加入V
Kruskal
思路: 并查集 O(NlogN)
- 对所有边排序
- 考虑每一条边的两个端点是否在同一并查集中
- 如果不联通则合并两个并查集
- 直到所有边都被检查, 或者所有节点都在同一个集合中(记录所有节点数做一次合并就减去一)
拓扑排序
并查集
- 集合存在代表元素, 但不关心具体是哪一个元素
常用操作
- 快速找到代表元素/合并两个集合
实现
- 树和路径压缩
前缀和
- 定义: 数组前N项的和: >$S[N]=a[1]+a[2]+\cdots+a[N]$<
用途:
- 快速得到区间和: >$S[M, N] = S[N] - S[M-1]$<
区间快速运算: 对>$[M, N]$<加上k
构造辅助数组aux[i], 表示>$[i, len(a)]$<区别的变化值
- 拆分成: >$[M, len(a)]$<加上k, >$[N+1, len(a)]$<减去k
- aux[M] = k, aux[N+1] = -k
- 求aux的前缀和即可知道每个位置的变化量