Matlab中矩阵B与f的计算复杂度阶数求解方法

前置判断 #

首先明确代码里各矩阵的结构和Matlab反斜杠运算符的逻辑：

• L = tril(A)是n阶稠密下三角矩阵，对角元均为1+rand(1,n)生成的正数，非奇异；U = A-L是n阶稠密严格上三角矩阵，主对角线及以下元素全为0。
• Matlab的\运算符会自动识别系数矩阵的结构，当系数矩阵为三角阵时，不会执行LU分解等额外操作，直接调用向前/向后替换算法求解线性方程组，不需要额外的分解开销。

f = L\b 的复杂度计算 #

• 该语句对应求解下三角线性方程组 L * f = b，其中右端项b是n×1的向量。
• 下三角方程组的向前替换（前代法）精确浮点运算量为n(n+1)/2次乘加操作，渐近时间复杂度为 O(n²)。
• 当n=1000时，该步骤总运算量约为5×10^5次浮点操作，开销极低。

B = -L\U 的复杂度计算 #

• 该语句对应求解矩阵方程 L * B = -U，其中右端项U是n×n的上三角矩阵，输出B也是n×n的稠密矩阵。
• 该操作本质是对U的每一列作为独立右端项，分别执行一次前代求解：
  • 如果不利用U的上三角结构（Matlab默认的稠密多右端三角求解逻辑），总精确浮点运算量为n²(n+1)/2次乘加操作，渐近时间复杂度为 O(n³)。
  • 如果额外利用U是严格上三角的特性（每列只有前j-1个元素非零，j为列号），可以把总运算量降到n³/6量级，但渐近复杂度仍为O(n³)，仅常数项降低。
• 注意：该操作不会通过计算L的逆再矩阵乘U的方式实现，但即使是求逆再相乘，渐近复杂度同样为O(n³)，仅常数项有差异。
• 当n=1000时，该步骤总运算量约为5×10^8次浮点操作，是代码预计算阶段的核心开销。

常见误区说明 #

不要直接套用稠密矩阵线性求解的2/3 n³复杂度：那个复杂度包含了稠密矩阵LU分解的开销，本问题中L已经是下三角形式，不需要做分解，因此三阶项的常数系数更低。

内容的提问来源于stack exchange，提问作者Rustless