矩阵乘法

概述

矩阵乘法 是线性代数中的基本运算，也是展示分治策略如何优化算法复杂度的经典案例。

定义

矩阵乘法

给定两个 $n\times n$ 矩阵 $A$ 和 $B$，其乘积矩阵 $C=A\times B$ 的每个元素为 $C_{ij}={\sum }_{k=1}^n{A}_{ik}{B}_{kj}$。

核心性质

• 朴素算法：三重循环，时间复杂度 $\Theta (n^3)$
• 分治方法：将矩阵分为4个子矩阵，递归计算8次 $(n/2)\times (n/2)$ 乘法，加上4次加法。递归关系为 $T(n)=8T(n/2)+\Theta (n^2)=\Theta (n^3)$，与朴素算法同阶
• Strassen改进：Strassen算法将递归乘法从8次减为7次，复杂度降至 $\Theta (n^{\lg 7})\approx \Theta (n^{2.81})$
• 下界：矩阵乘法的下界仍为开放问题，已知最优算法复杂度低于 $O(n^{2.373})$
• 分治分析价值：朴素分治虽未改进复杂度，但为理解Strassen算法的优化提供了基线

章节扩展

第4章：4.1 矩阵乘法引入朴素分治方法，4.2 Strassen算法在此基础上通过减少递归乘法次数实现突破，是分治策略章节的核心案例。

参见

• 4.1 矩阵乘法 — 朴素方法与分治基线
• 4.2 Strassen算法 — Strassen的优化方法
• 主定理 — 分析分治递归关系的工具