用时间复杂度和空间复杂度衡量一个算法的时间效率和空间效率。

描述时空复杂度时，通常使用渐进符号表示，因此一般只考虑时空复杂度函数中的最高阶项。

简便地，通常只使用 $O$ 描述时空复杂度。

所以，描述时空复杂度时，通常会忽略常数，例如 $100n$ 和 $n$ 均为 $O(n)$。

但是程序的实际执行效率却会受常数影响，而在部分情况下，这一部分的影响并不能忽略。

与一般“卡常”文章相比，本文着重于相同做法下的不同实现导致的常数差异，侧重于讨论小常数代码习惯，而非通常的“硬件优化”。

部分情况下一份常数优秀的时间复杂度更劣的代码，实际运行效率反而优于时间复杂度更优秀的大常数做法，例如重链剖分+数据结构的双 $\log$ 绝大多数情况下都优于 LCT 的单 $\log$。

STL 常数

众所周知 STL 常数远大于手动实现。尽管现在各平台/比赛大都已经不限制 O2 优化，但是 STL 的常数真的很优秀吗？

测试环境为：2025.9.11 洛谷的 C++20 O2，简单测试，均进行一次测试（实际上测了多次，波动不大的就取第一次）插入元素均为 $[1,n]$。

注：不同平台、编译环境会导致实际情况不同，以下测试数据仅供参考。

容器	1e6 次操作 int	5e6 次操作 int	空的 5e6 个 不使用	5e6 个，每个一个元素
vector	psuh_back 17ms 5MB	push_back 20ms 33MB	10ms <1MB（因为 vector 没有被使用，所以被编译器优化了，实际占用 120 MB 左右）	push_back 300ms 267MB
vector	reserve 7ms 4MB	reserve 12ms 19MB	/	/
deque	push_back 7ms 4MB	push_back 20ms 20MB	>251ms >512MB	/
list	push_back 46ms 31MB	push_back 208ms 153MB	48ms 115MB	push_back 254ms 268MB
priority_queue	push 33ms 5MB	push 172ms 32 MB	60ms 153MB	push 272ms 306MB
set	insert 241ms 46MB	insert 1.53s 229 MB	89ms 229MB	insert 348ms 459MB
unordered_set	insert 78ms 42MB	insert 356ms 198MB	106ms 267MB	insert >312ms >512MB

注：

• queue 和 stack 默认是对 deque 的包装，所以效率默认和 deque 一致，可以修改底层容器，使用 list 作为底层容器，效率和 list 一致。
• priority_queue 是对 vector 的包装，所以效率默认和 vector 一致，但是 priority_queue 功能是堆，所以时间复杂度需要多 $\log n$。
• multiset、multimap、map 和 set 实现相同，时空效率一致。unordered 容器同理。

其中，vector、deque、list 通常具有相同的功能，priority_queue 和 set 存在相同功能，因此将分成两部分进行更多的测试。

注：因为 list 插入 5e7 个元素内存过大，所以 list 只插入 1e7 个元素。

容器	插入 5e7 个元素	遍历 5e7 个元素	插入 5e7 个元素并 rand()	随机访问 5e7 次
数组/array	赋值 5ms	auto 75ms	769ms	1.97s
vector	push_back 180ms	auto 200ms	920ms	2.44s
deque	push_back 160ms	auto 190ms	880ms	3.95s
list	push_back 420ms	auto 450ms	560ms	不支持随机访问

容器	插入 1e6 个元素并删除	插入 5e6 个元素并删除
set	310ms	1.82s
priority_queue	80ms	430ms

综上，在不同需求下，使用不同常数的 STL 会有不错的效果。

数组下标访问

多维数组在内存中是按行优先连续存储的。

如果遍历时没有按照最右维向左的顺序，那么每次访问内存时不连续，会极大地降低 CPU 缓存命中率。

应用场景主要是多维 dp 时，考虑 dp 状态维度的设计，使得最内层的循环位于数组的最右侧。

一个经典的场景是 ST 表预处理，以洛谷 P3865 为例 $N={10}^5$：

• 按行遍历：最慢点 300ms
• 按列遍历：最慢点 440ms

快速读入

这里需要比较的只有 关流 cin 和 fread 快读，默认 $|a_i|\le n$

读入方式	$n={10}^5$	$n={10}^6$	$n={10}^7$	$n={10}^8$
scanf	10ms	72ms	700ms	>2.7s
cin 关流	9ms	58ms	565ms	>2.7s
getchar	6ms	30ms	290ms	>2.7s
fread	5ms	16ms	133ms	1.39s

同时，因为部分平台问题，实际情况会有差异。

快速取模

取模方式	P3373 线段树 2	5e8 次 rand×rand 求和
不取模	78ms	5.75s
直接取模	460ms	7.17s
const	103ms	6.21s
Barret	119ms	6.44s

根据实验容易发现 const 本身优化足够优秀，仅在读入模数时需要考虑取模优化。

小常数数据结构

树状数组 < 线段树 < 平衡树

数据结构	P3372 线段树 1
树状数组	31ms
zkw线段树	41ms
递归式线段树	72ms
平衡树	154ms

枚举变量的上下界

部分情况下，枚举变量时可以避免一些冗余的情况。

例如求二元组 $(i,j),i,j\in [1,n]$ 时，可以钦定 $i\le j$，那么可以优化 $\frac{1}{2}$ 的常数。

枚举二维坐标时，钦定 $x_2\ge x_1,y_2\ge y_1$，那么可以优化 $\frac{1}{6}$ 的常数，$n=100$ 时，${10}^8$ 的枚举量优化后仅有 ${10}^7$。

dfs 搜索时，可以在递归的过程中顺带计算信息，而非在递归边界从头算一遍信息。

位运算