算法基础课第七讲总结
作者：
zmj2008
,
2020-03-31 18:01:25
,
所有人可见
,
阅读 1997
算法基础课第七讲总结
或者这里
1. 第一讲里的时间复杂度分析
| 算法名称 |
时间复杂度 |
扩展算法 |
时间复杂度 |
| 快速排序 |
$O(Nlog(N))$ |
求第$k$小的数 |
$O(N)$ |
| 归并排序 |
$O(Nlog(N))$ |
求逆序对 |
$O(Nlog(N))$ |
|
|
|
|
| 二分 |
$O(log(N))$ |
|
|
|
|
|
|
| 高精度加法 |
$O(A的长度 + B的长度)$ |
高精度减法 |
$O(A的长度 + B的长度)$ |
| 高精度乘低精度 |
$O(A的长度)$ |
高精度除以低精度 |
$O(A的长度)$ |
|
|
|
|
| 一维前缀和 |
$预处理O(N), 查询O(1)$ |
二维前缀和 |
$预处理O(N^2), 查询O(1)$ |
| 一维差分 |
$预处理O(N), 查询O(1)$ |
二维差分 |
$预处理O(N), 查询O(1)$ |
|
|
|
|
| 双指针 |
$O(N)$ |
将$O(N^2)$的暴力做法优化到$O(N)$ |
$O(N)$ |
| 位运算 |
$O(1)$ |
|
|
|
|
|
|
| 离散化 |
$令X=N+2M, 则为O(Xlog(X))$ |
将大范围里的数映射到$1$~$n$ |
|
| 区间合并 |
$O(Nlog(N))$ |
|
|
2. 第二讲里的时间复杂度分析
| 算法名称 |
时间复杂度 |
扩展算法 |
时间复杂度 |
| 模拟单链表 |
$O(N)$ |
模拟双链表 |
$O(N)$ |
| 模拟栈 |
$O(N)$ |
模拟队列 |
$O(N)$ |
|
|
|
|
| 单调栈 |
$O(N)$ |
|
|
| 单调队列 |
$O(N)$ |
滑动窗口中的最大值 |
$O(N)$ |
|
|
|
|
| KMP |
$O(N)$ |
|
|
| Trie |
$插入O(S.size()), 查询O(S.size())$ |
最大异或对 |
$插入O(32), 查询O(32)$ |
|
|
|
|
| 并查集 |
$预处理O(N), 合并、判断是否在一个集合中O(1)$ |
|
|
| 并查集 |
$查询所在集合的元素个数、查询到祖宗节点的路径长度O(1)$ |
|
|
| 堆 |
$预处理O(N), up操作、down操作O(log(N))$ |
堆排序 |
$O(Nlog(N))$ |
| 堆 |
$插入操作、删除操作、修改操作O(log(N)$ |
|
|
| 哈希表 |
$插入O(1), 查询O(1) (平均时间)$ |
|
|
| 字符串哈希 |
$预处理O(S.size()), 判断两个字串是否一样O(1)$ |
|
|
3. 第三讲里的时间复杂度分析
| 算法名称 |
时间复杂度 |
扩展算法 |
时间复杂度 |
| DFS |
$依具体题目而定$ |
求全排列、$n$皇后问题 |
$O(N!N)、O(N!N^2)$ |
| BFS |
$依具体题目而定$ |
走迷宫、八数码 |
$大于O(N^2)、实测单点平均332ms$ |
| 树和图的DFS |
$O(M)$ |
求树的重心 |
$O(N)$ |
| 树和图的BFS |
$O(M)$ |
求图中点的层次 |
$O(M)$ |
| 拓扑排序 |
$O(M)$ |
|
|
|
|
|
|
| Dijkstra |
$O(N^2)$ |
Dijkstra堆优化 |
$O(Mlog(M))$ |
| Bellman_ford |
$O(NM)$ |
求经过不超过$K$边的最短路 |
$O(KM)$ |
| spfa |
$一般O(KM), 最坏O(NM)$ |
判断图中有无负环 |
$一般O(KM), 最坏O(NM)$ |
| Floyd |
$O(N^3)$ |
求每两个点之间的最短路 |
$预处理O(N^3), 查询O(1)$ |
|
|
|
|
| Prim |
$O(N^2)$ |
Prim堆优化 |
$O(Mlog(M))$ |
| Kruskal |
$O(Mlog(M))$ |
|
|
|
|
|
|
| 染色法 |
$O(M)$ |
|
|
| 匈牙利算法 |
$一般O(KM), 最坏O(NM), 但是总体表现优秀$ |
|
|
4. 第四讲里的时间复杂度分析
| 数学板块 |
算法1 |
时间复杂度 |
算法2 |
时间复杂度 |
| 质数 |
试除法 |
$O(√N)$ |
分解质因数 |
$O(√N)$ |
| 质数 |
线性筛法 |
$O(N)$ |
|
|
| 约数 |
试除法 |
$O(√N)$ |
约数个数 |
$O(√N)$ |
| 约数 |
约数之和 |
$O(√N)$ |
最大公约数 |
$O(log(A))$ |
|
|
|
|
|
| 欧拉函数 |
试除法 |
$O(√N)$ |
筛法求欧拉函数 |
$O(N)$ |
| 快速幂 |
快速幂 |
$O(log(b))$ |
求模数为质数的数的逆元 |
$O(log(Mod))$ |
| 扩展欧几里得算法 |
扩展欧几里得 |
$O(log(A))$ |
求线性同余方程的一组解 |
$O(log(A))$ |
|
|
|
|
|
| 中国剩余定理 |
中国剩余定理 |
$O(Nlog(a_1a_2…a_n))$ |
求解同余方程组 |
$O(Nlog(M))$ |
| 高斯消元 |
求解线性方程组 |
$O(N^3)$ |
求解异或线性方程组 |
$O(N^3)$ |
|
|
|
|
|
| 组合数 |
递推式 |
$预处理O(N^2), 查询O(1)$ |
预处理阶乘与阶乘模$Mod$的逆元 |
$预处理O(Nlog(Mod)), 查询O(1)$ |
| 组合数 |
$Lucas$定理 |
$O(b \times log_p(a) \times log(p))$ |
|
|
| 组合数 |
分解质因数+高精度乘低精度 |
$O(a \times res.size())$ |
求$Catalan$数 |
$O(b \times log(Mod))$ |
| 容斥原理 |
$1$~$N$之中能被质数$p_1,p_2,…,p_n$整除的个数 |
$O(2^NN)$ |
|
|
|
|
|
|
|
| $Nim$游戏 |
$Nim$游戏 |
$O(N)$ |
台阶$Nim$游戏 |
$O(N)$ |
| $Nim$游戏 |
集合$Nim$游戏 |
$O(M)$ |
拆分$Nim$游戏 |
$O(N^2)$ |
5. 第五讲里的时间复杂度分析
| 算法 |
时间复杂度 |
优化 |
时间复杂度 |
| 01背包 |
$O(NV)$ |
|
|
| 完全背包 |
$O(NV)$ |
|
|
| 多重背包 |
$O(NVs_i)$ |
二进制优化 |
$O(NVlog(s_i))$ |
| 分组背包 |
$O(NVs_i)$ |
|
|
|
|
|
|
| 数字三角形 |
$O(N^2)$ |
|
|
| 最长上升子序列 |
$O(N^2)$ |
二分优化 |
$O(Nlog(N))$ |
| 最长公共子序列 |
$O(N^2)$ |
|
|
| 最短编辑距离 |
$O(N^2)$ |
|
|
|
|
|
|
| 石子合并 |
$O(N^4)$ |
前缀和优化 |
$O(N^3)$ |
|
|
|
|
| 计数问题 |
$O(log(N))$ |
|
|
|
|
|
|
| 蒙德里安的梦想 |
$O(4^NN)$ |
|
|
| 最短Hamilton路径 |
$O(2^NN^2)$ |
|
|
|
|
|
|
| 没有上司的舞会 |
$O(N)$ |
|
|
|
|
|
|
| 滑雪 |
$O(N^2)$ |
|
|
6. 第六讲里的时间复杂度分析
| 问题类型 |
算法1 |
时间复杂度 |
算法2 |
时间复杂度 |
| 区间问题 |
区间选点 |
$O(Nlog(N))$ |
最大不相交区间数量 |
$O(Nlog(N))$ |
| 区间问题 |
区间分组 |
$O(Nlog(N))$ |
区间覆盖 |
$O(Nlog(n))$ |
| Huffman树 |
合并果子 |
$O(Nlog(N))$ |
|
|
| 排序不等式 |
排队打水 |
$O(Nlog(N))$ |
|
|
| 绝对值不等式 |
货仓选址 |
$O(Nlog(N))$ |
|
|
| 推公式 |
耍杂技的牛 |
$O(Nlog(N))$ |
|
|
666666
6666
%%%