第4章：算法复杂度分析：时间复杂度和空间复杂度、访存密集型 vs 计算密集型算子、Roofline模型入门
各位同学，欢迎来到第四章。这一章，我们要聊点“硬核”的东西。
说实话，很多做算子优化的朋友，一上来就撸代码，调参数，结果调了半天性能纹丝不动。为什么？因为没搞清楚问题的本质。我个人习惯，拿到一个算子，先不急着写代码，而是先做三件事：算复杂度、看瓶颈、画Roofline。这三板斧下去，问题基本就清晰了。
4.1 时间复杂度与空间复杂度：老生常谈，但你真的懂吗？
时间复杂度，说白了就是“这个算法跑得快不快”。空间复杂度，就是“这个算法吃内存多不多”。
你可能会说：“这谁不知道啊？” 嗯，但我在项目中遇到过不少同学，把O(n²)的算法写成了O(n³)，还浑然不觉。比如矩阵乘法，最朴素的实现是三层循环，复杂度O(n³)。但你想想看，如果能把其中一层循环优化掉，变成O(n²)，那性能提升可不是一星半点。
- 时间复杂度：关注循环层数和数据规模。常见的有O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(n³)等。
- 空间复杂度：关注额外开辟的存储空间。比如是否使用了临时数组、缓存等。
- 权衡：很多时候，时间复杂度和空间复杂度是“鱼和熊掌”的关系。用空间换时间，或者用时间换空间，需要根据场景选择。
举个例子，计算斐波那契数列。递归写法时间复杂度O(2ⁿ)，空间复杂度O(n)。而动态规划写法，时间复杂度O(n)，空间复杂度O(1)。你看，这就是典型的“用空间换时间”的优化。
// 递归写法（时间复杂度高）
int fib_recursive(int n) {
if (n <= 1) return n;
return fib_recursive(n-1) + fib_recursive(n-2);
}
// 动态规划写法（空间换时间）
int fib_dp(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
4.2 访存密集型 vs 计算密集型算子：你的算子到底“卡”在哪？
这是算子优化里最核心的一个分类。我经常问团队的新人：“你觉得这个算子是访存密集还是计算密集？” 如果答不上来，那优化方向大概率是错的。
访存密集型算子：说白了，就是“数据搬运”比“计算”更耗时。比如向量加法、矩阵转置、数据拷贝等。这类算子的瓶颈在内存带宽，而不是计算单元。
计算密集型算子：就是“计算”比“数据搬运”更耗时。比如矩阵乘法、卷积、FFT等。这类算子的瓶颈在计算单元（比如ALU、MAC单元），而不是内存带宽。
我曾经优化过一个图像处理算子，一开始拼命优化计算逻辑，结果性能纹丝不动。后来一分析，发现是访存密集型的——数据从内存到缓存的搬运占了90%的时间。于是我把优化方向改为“数据复用”和“缓存友好”，性能直接提升了5倍。嗯，方向对了，事半功倍。
| 类型 | 特点 | 典型算子 | 优化方向 |
|---|---|---|---|
| 访存密集型 | 计算量小，数据搬运量大 | 向量加法、数据拷贝、矩阵转置 | 减少访存次数、提高缓存命中率、使用DMA |
| 计算密集型 | 计算量大，数据搬运量小 | 矩阵乘法、卷积、FFT | 提高计算并行度、使用SIMD、优化循环 |
4.3 Roofline模型入门：一张图看懂性能瓶颈
Roofline模型，说白了就是一张“性能天花板”图。它把算子的性能（FLOPS）和计算强度（FLOP/Byte）画在一起，告诉你：你的算子到底是被计算能力限制，还是被内存带宽限制。
我第一次接触Roofline模型时，觉得这东西太抽象了。后来在项目中用它分析一个卷积算子，才发现它有多实用。你想想看，一张图就能告诉你“瓶颈在哪”，省了多少瞎猜的时间。
- 计算强度 = 总计算量（FLOP） / 总访存量（Byte）
- 性能上限 = min(计算峰值, 带宽峰值 × 计算强度)
下面这张SVG图，展示了Roofline模型的基本结构。横轴是计算强度，纵轴是性能（FLOPS）。斜线部分表示“带宽受限”，水平线部分表示“计算受限”。
这张图怎么看？很简单：
- 如果你的算子落在斜线区域，说明它被内存带宽限制了。优化方向是减少访存、提高数据复用。
- 如果你的算子落在水平线区域，说明它被计算能力限制了。优化方向是提高计算并行度、使用更高效的指令。
- 如果你的算子落在拐点附近，说明它已经接近最优了，再优化空间不大。
4.4 实战：用Roofline分析一个矩阵乘法算子
咱们来点实际的。假设你有一个矩阵乘法算子，输入是1024×1024的矩阵。我们来算一下它的计算强度和性能。
// 矩阵乘法：C = A * B
// 假设所有矩阵都是 float 类型（4字节）
// 计算量：2 * N^3 = 2 * 1024^3 ≈ 2.15 GFLOP
// 访存量：3 * N^2 * 4 = 3 * 1024^2 * 4 ≈ 12.58 MB
// 计算强度 = 2.15 GFLOP / 12.58 MB ≈ 171 FLOP/Byte
这个计算强度是171 FLOP/Byte。假设你的硬件计算峰值是1 TFLOPS，内存带宽是100 GB/s。那么：
- 带宽限制下的性能 = 100 GB/s × 171 FLOP/Byte ≈ 17.1 TFLOPS
- 但计算峰值只有1 TFLOPS，所以实际性能上限是1 TFLOPS。
你看，这个矩阵乘法算子明显是计算密集型的。优化方向应该是提高计算并行度，比如使用SIMD指令、多线程、或者利用GPU的Tensor Core。
4.5 本章小结
这一章，我们聊了三个核心概念：
- 时间复杂度和空间复杂度：帮你从宏观上评估算法的效率。
- 访存密集型 vs 计算密集型：帮你找到算子的瓶颈所在。
- Roofline模型：帮你用一张图看清性能天花板。
记住，算子优化不是瞎调参数，而是有方法论的。先分析复杂度，再判断瓶颈类型，最后用Roofline模型验证。这套流程走下来，你的优化方向就不会跑偏。
好了，这一章就到这里。下一章，我们会深入具体的优化技巧，比如循环展开、数据对齐、缓存优化等。到时候见。