我在乡间的小路上 社会的边缘里 抓狂般的想念与你炽热的友情在寒冷的雨滴下和黑色月光萦绕留下妖娆的树影中间 起舞赞美酷爱的这个一团乱麻的世界
-《白色帽子墨镜丝袜皮鞋和你的大衣,红色思念忐忑缠绵与我难忘的记忆》
cpp一秒 10^7-10^8
一千万到一亿次
原文摘录
一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下,C++代码中的操作次数控制在 $10^7 \sim 10^8$ 为最佳。
下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:
$n \le 30$, 指数级别, dfs+剪枝,状态压缩dp
$n \le 100$ => $O(n^3)$,floyd,dp,高斯消元
$n \le 1000$ => $O(n^2)$,$O(n^2logn)$,dp,二分,朴素版Dijkstra、朴素版Prim、Bellman-Ford
$n \le 10000$ => $O(n * \sqrt n)$,块状链表、分块、莫队
$n \le 100000$ => $O(nlogn)$ => 各种sort,线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
$n \le 1000000$ => $O(n)$, 以及常数较小的 $O(nlogn)$ 算法 => 单调队列、 hash、双指针扫描、BFS、并查集,kmp、AC自动机,常数比较小的 $O(nlogn)$ 的做法:sort、树状数组、heap、dijkstra、spfa
$n \le 10000000$ => $O(n)$,双指针扫描、kmp、AC自动机、线性筛素数
$n \le 10^9$ => $O(\sqrt n)$,判断质数
$n \le 10^{18}$ => $O(logn)$,最大公约数,快速幂,数位DP
$n \le 10^{1000}$ => $O((logn)^2)$,高精度加减乘除
$n \le 10^{100000}$ => $O(logk \times loglogk),k表示位数$,高精度加减、FFT/NTT
判断时间复杂度的方法
1.判断循环次数 $O(n+m)$ 两维 $O(n^2)¥ [DP]
2.递归 主定理 [快排 归并排序]
典型例题分析
基础算法
- 快排[可能$(log n)$层 ] 归并排序 [一定$(logN)层]
- 二分 对半分 会迭代$O(logn)$次
- 双指针算法 两种循环 $O(n)$ 里边j只加不减
数据结构
- 单链表 O(1)删掉某个数 栈和队列 也都是O1的
- 单调栈/单调队列 看着是两层循环 但是每个元素最多进出栈一次 那么
--
只会执行O(n)次 所以是线性的 - Kmp i每增加1 j最多增加1 j=ne[j]起码会减去1 因此Kmp也是线性的
- Trie 线性的
- 并查集 这个记住就可以了 我们有 路径压缩 [ 按秩合并 ]的存在 并查集的时间效率就会变成 $(nlogn)$ [ $nloglogn$ ] 的效率 实际上最坏是$O(logn)$的
- 堆 返回最小值 $O(1)$ 插入 需要进行
DOWN
或者UP
操作 [堆是一颗完全二叉树] 走到顶部 时间复杂度和堆的高度$O(logn)$成正比的 删除添加就是$O(logn)$ - 哈希表 最坏的是很坏 但是基本上几乎不会遇见(和小行星撞击地球的概率是一样的) 增删改查 平均效率是$O(1)$的
搜索与图论
搜索的计算量
算一下这个函数执行多少次就可以了
- DFS
-树根拓展n个点 拓展到最后一个点 最后一层的点共 $n!$个点 倒数第一层是 $(n-1)!$个点
每层的计算量 最后一层输出答案需要$O(n)$ 最后一层是$n!n$ 倒数第一层 是 $(n-1)!n$ 总共 $(n!+(n-1)!+…)n$ 因为不是最后一层还是需要循环n 都是乘以一个 n
那么 由于相对于$n!$其他项都是无穷小量 总共效率就是 $n!n$ - BFS 这两个都是画一棵树来看
- 树与图的深度优先遍历 图的方法 我们保证每个点只会遍历一次 那么效率 是 n个点 每个点的边就是 遍历所有边 m 那么深度宽度优先遍历就是 $O(n+m)$
- 树与图的广度优先遍历
- 拓扑排序 基于宽搜和深搜 所以都是 $O(n+m)$
- Dijkstra
-朴素 两种循环 $O(n^2)$
-堆优化版的 每个点只会被遍历一次 就是对每个点的所有边就是所有边m 循环体内最多执行m次 插了m次总个数是m级别的 内层是 $mlogm$ 由于 $m \le n^2$
因此 $mlogm \le 2mlogn$ 可以看成 $mlogn$的效率 - bellman-ford 两重循环 总共$O(nm)$
- spfa
-最坏 $O(nm)$ 并且可以被卡 理论非常高 但是运行效率非常好 [ 二分图匈牙利 最大流算法]
-判负环 mn的 但是比求最短路要长很多 (两者看起来时间复杂度一样) - Floyd 三重循环 $O(n^3)$
- Prim 两重循环 $O(n^2)$
- Kruskal 有一个排序 $mlogm$ 还有个循环 $O(m)$ 所以整个时间复杂度是 $mlogm$
- 染色法判定二分图 图的深搜或者宽搜 效率是 $O(n+m)$
- 匈牙利算法 理论时间复杂度 每个点循环一次 需要$O(n)$ 判断的时候 需要判断所有点的所有边 这个时间效率就是$O(nm)$ 而m最坏是$n^2$ 所以匈牙利算法最坏是$O(n^3)$
但是 实际上运行效率非常快
long long
范围的数是 $10^18$ 那么$log10^18$就是64 有个小技巧就是 $(log_210^x\approx3x)$
那么 $(log_210^{18} \approx54 \approx60)$
数学知识
-
质数
-试除法 $2-\sqrt(x)$ 那么时间复杂度就是$O(\sqrt(x))$
-分解质因数 $O(\sqrt(x))$
-筛质数 艾什筛法 $\frac{n}{1}+\frac{n}{2}+…+\frac{n}{n}$ 后边是调和级数 =$lnn+c$ [c是欧拉常数 0.577] 但是是$O(logn)$级别 那么总的时间复杂度就是 $O(nlogn)$
-补充一点 如果是 $\frac{n}{2}+\frac{n}{3}++\frac{n}{5}+\frac{n}{7}…+\frac{n}{n}$ 近似等于 $O(loglogn)$ -
约数 最大公约数 辗转相除法 背过 $O(logn)$级别的
- 欧拉函数
- 快速幂 $O(logK)$ 很好算
- 扩展欧几里得算法
- 中国剩余定理
- 高斯消元
- 求组合数
- 容斥原理
- 博弈论
动态规划
动态规划除了看循环几层 还有一个常用的技巧
动态规划问题的计算量 = 状态数量 * 状态转移的计算量
- 背包问题 循环几层 就是几次方
- 线性DP 最长上升子序列2 两重循环 外层 n次 内层 $logn$次 所以整个效率是$O(nlogn)$次
- 区间DP
- 计数类DP
- 数位统计DP
- 状态压缩DP 蒙德里安的梦想 外层循环 $2n^2$ 内层 $O(n)$ 所以总共就是 $O((2^n)^2n)$
- 树形DP 没有上司的舞会 看着$O(n)$个状态 每个状态循环1次 看似$n^2$(dfs)的效率 但是每个点只会被遍历一次 就是把每个点的所有边遍历一次 就是所有边的数量 所以总共效率是$O(n)$ 线性的
- 记忆化搜索等内容 滑雪 两维 每个状态需要多少时间 4次 O1的时间 所以就是 $O(n^2)$
动态规划这部分的解释都比较详细 可以看笔记
贪心
都是一个排序加一个循环 排序 logn 循环几层就是多少
1. 区间问题
2. Huffman树
3. 排序不等式
4. 绝对值不等式
5. 推公式
空间复杂度
64M
1 Byte=8 bit
1 KB=1024 Byte
1 MB=1024*1024 Byte
1 MB=1024*1024*1024 Byte
int = 4 Byte ==> 64MB = 2^24 => 1千600万 程序的其他地方也要用空间 函数调用和库 不要恰好开满64MB空间 最多用到50M差不多了
char = 1 Byte
double,long long =8 Byte
指针 32是4 Byte 64是8 Byte
bool 1 Byte 不是1位
流量是兆位 8M=>1MB/s
统计方法
int v[N],w[N];
int f[N];
cout<<(sizeof v+sizeof w+sizeof f)<<endl; ==>12120Byte 字节
cout<<(sizeof v+sizeof w+sizeof f)/1024<<endl; ==>12120/1024 KByte 千字节
cout<<(sizeof v+sizeof w+sizeof f)/1024/1024<<endl; ==>12120/1024/1024 MByte 兆字节
开了114M 但是没有爆内存呢 因为操作系统的优化 开了这么多 用的时候不会一下子都给你
当你用到的的时候没有分配会马上给你分配一块 只开没有用的话 一般也没事
我们刷一遍一般就有事了 memset(v/w/f,0,sizeof v/w/f)
栈空间
递归也是需要空间的
快排没有多余数组 默认认为快排额外空间复杂度 $(O1)$的 归并是$O(n)$的 这样是不对的
快排会递归$logn$层 所以快排额外空间是 $O(logn)$
2024-2-04
枕头里藏满了发了霉的梦,梦里住满了无法拥有的人。
逐渐明白很多事都是无法控制的 凡事也开始不再以自我为中心
没有进行某件事的动力 只是因为被拒绝习惯了
慢慢悠悠的走着的时候 惆怅充满内心溢于言表 当你我不在那里相聚 我们将在哪里
-<啄木鸟小姐还会留下她的姓名吗>
哎哟小情郎你莫愁 此生只为你挽红袖
哎呦小娘子你莫忧 待到春来又雪满楼
不负天长不负地久 你我白首
-《鸳鸯戏》
以声之色,塑花之形,将你之名,刻于我心。
无论是Gensei的尾声,还是一段故事的结局,难过的不过是相聚不会继续
但我们都希望 这段回忆再次提及的时候,不会BE,
当我们离别时,希望我们永远可以再见,
从月亮被提及的那天起,声音的形状就是喜欢你。
-<声之形>
人不能同时拥有青春和对青春的感受
大学生毕业以后 男的送外卖 女的搞直播 送外卖的休息时间看直播 搞直播的饿了开始点外卖
送外卖的挣了钱用来打赏 搞直播的挣了钱用来点外卖 20岁的男生贫困潦倒 20岁的女生风华正茂
十五六岁的我在地理试卷上写下此地的优势在于其丰富的廉价劳动力 十年后我奔波在上班的路上
听到背后传来隐隐约约的风声 我停下身来转过身去 一颗来自十年前的子弹正中眉心
小时候你以为杀掉的呆滞玩家是人机 殊不知那是未来下班后疲惫的自己
小时候觉得那些寓言故事很讽刺 长大后才知道刻舟求剑是遗憾 掩耳盗铃是欺骗 削足适履是将就
邯郸学步是从众 如果我没有读过书 我可以去找别的活干 可我知道的太多了 思考得太多了
产生了不被周围人所理解的苦恼 学历不仅仅是敲门砖 也是我下不来的高台 更是脱不下长衫的孔乙己
在所谓体面与生活反复挣扎时 多么心酸只有自己知道 这个世界上最没用的是面子 最难脱下的也是长衫
过了多年以后我站上了讲台 发现了不听话的学生 于是我走向了讲台 发现管教的不是我的学生
而是当时年少的自己 教育具有长期性和滞后性 也许多年后的一个瞬间才会意识到 那一刻也是子弹命中的瞬间
教育也在此刻完成了闭环
-《白色帽子墨镜丝袜皮鞋和你的大衣,红色思念忐忑缠绵与我难忘的记忆》
新年好!诸位!!!