Strassen 矩阵乘法体现了什么分治思想？为什么能少做一次乘法？
简化版
Strassen 矩阵乘法是分治优化矩阵乘法的经典例子。
普通分块矩阵乘法把矩阵分成 4 块后，需要 8 次子矩阵乘法；Strassen 通过重新组合加减法，只做 7 次乘法。
乘法次数减少后，复杂度从 O(n^3) 降到约 O(n^2.807)，但常数和数值稳定性代价更高。
详细版
普通矩阵乘法分块后：
C11 = A11B11 + A12B21
C12 = A11B12 + A12B22
C21 = A21B11 + A22B21
C22 = A21B12 + A22B22这里有 8 次子矩阵乘法。
Strassen 构造 7 个中间乘积 M1..M7，再通过加减组合得到 C11..C22。
它体现的分治思想是：递归处理更小矩阵，同时通过代数变形降低每层最贵的乘法次数。
完整版教学
一、普通矩阵乘法为什么是 O(n^3)
两个 n x n 矩阵相乘，结果矩阵有 n^2 个元素。每个元素要做一行和一列的点积，成本是 O(n)。因此普通算法复杂度是 O(n^3)。分治的想法是把矩阵切成 4 个 n/2 x n/2 的小矩阵，再递归相乘。
记忆钩子：Strassen 的突破点不是不分块，而是分块后少做一次乘法。
二、普通分块为什么需要 8 次乘法
把矩阵切成四块：
A = [A11 A12] B = [B11 B12]
[A21 A22] [B21 B22]结果的每一块都由两个乘积相加得到，一共 4 个结果块，每块 2 次乘法，所以是 8 次子矩阵乘法。
| 结果块 | 普通计算 |
|---|---|
C11 | A11B11 + A12B21 |
C12 | A11B12 + A12B22 |
C21 | A21B11 + A22B21 |
C22 | A21B12 + A22B22 |
递推式是 T(n)=8T(n/2)+O(n^2)，解出来仍是 O(n^3)。
三、Strassen 如何少一次乘法
Strassen 通过 7 个中间乘积重组结果：
M1 = (A11 + A22)(B11 + B22)
M2 = (A21 + A22)B11
M3 = A11(B12 - B22)
M4 = A22(B21 - B11)
M5 = (A11 + A12)B22
M6 = (A21 - A11)(B11 + B12)
M7 = (A12 - A22)(B21 + B22)然后用这些 M 通过加减得到四个结果块。它用更多加减法换掉一次昂贵乘法。
四、复杂度为什么变成 n^2.807
Strassen 的递推式是：
T(n) = 7T(n/2) + O(n^2)根据主定理：
T(n) = O(n^log2(7)) ≈ O(n^2.807)指数从 3 降到约 2.807，在大规模矩阵上理论优势明显。
五、代价和工程取舍
Strassen 并不是所有场景都比普通乘法快。它引入了更多矩阵加减、额外临时空间和更复杂的内存访问模式。浮点数场景还可能有数值误差放大的问题。因此工程实现通常在矩阵足够大时才切到 Strassen，小矩阵仍使用普通乘法或高度优化的 BLAS。
大规模：乘法减少带来收益
小规模：常数和内存开销可能更大
浮点：需要关注数值稳定性算法复杂度更优，不等于所有输入上都更快。
六、常见误区与追问
- 误区：认为 Strassen 不需要加减法。 它减少乘法，但增加了不少矩阵加减。
- 误区：看到 O(n^2.807) 就认为永远更快。 常数、缓存和内存分配会影响实际性能。
- 误区：普通分块分治能降低复杂度。 普通 8 次乘法的递推仍然是
O(n^3)。 - 追问：为什么乘法比加法更值得减少？ 在矩阵分治层面，子矩阵乘法递归成本更高，是主导项。
- 追问：面试要背 M1 到 M7 吗？ 通常重点是理解“7 次乘法 + 主定理复杂度”，公式可按岗位深度决定。
这些问题考察的是分治递推和工程取舍，而不是死背公式。
七、加强记忆
Strassen 记成“普通分块 8 乘，代数重组 7 乘”。普通分块虽然用了分治，但递推还是 8T(n/2)+O(n^2)，复杂度没降；Strassen 用更多加减换少一次乘法，递推变成 7T(n/2)+O(n^2)，指数降到约 2.807。但真实工程要看规模、常数、内存和数值稳定性。