关于Eigen中sumtrv1函数渐近复杂度分析的疑问

算力阿峰

2026-5-6

问题分析：代码渐近复杂度的误解点

首先先看你给出的代码：

double sumtrv1(const Eigen::MatrixXd &A, const Eigen::VectorXd &b) { 
    const int n = A.cols(); 
    assert((A.rows() == n) && (b.size() == n)); 
    return b.transpose() * A.triangularView<Eigen::Upper()>.solve(Eigen::MatrixXd::Identity(n,n)) * b; 
}

你的分析思路里的核心错误在于对上三角矩阵求逆操作的复杂度判断，咱们一步步理清楚：

错误点拆解

你认为“求该上三角矩阵的逆花费O(n²)”，这是关键误解。实际上，代码里的triangularView<Eigen::Upper()>.solve(Eigen::MatrixXd::Identity(n,n))并不是直接“求逆”，而是等价于求解n个独立的上三角线性方程组：
对于单位矩阵的每一列e_i（第i个元素为1，其余为0），我们需要解U x_i = e_i（U是A的上三角部分），得到的x_i就是U逆矩阵的第i列。
单个上三角方程组的回代求解复杂度是O(n²)（需要从最后一行向前递推，总共需要n+(n-1)+...+1 = O(n²)次运算）。n个这样的方程组，总时间复杂度就是n * O(n²) = O(n³)。

剩余步骤的复杂度验证

转置操作：确实如你所说，Eigen里的矩阵转置只是切换存储视图，没有实际运算开销，可以忽略。
获取上三角部分：triangularView只是创建一个视图，不复制数据，无额外代价，这部分你的判断是对的。
计算b.transpose() * U_inv * b：先计算U_inv * b（O(n²)），再计算转置后的b与这个结果的点积（O(n)），总复杂度O(n²)，相对于前面的O(n³)可以忽略。