algorithm - 如何计算给定算法的时间复杂度(岭回归)？

Question

我有以下表达式，我需要计算这个算法的时间复杂度。谁能帮助获得该算法的正确时间复杂度。

% save a matrix-vector multiply
Atb = A'*b;

% cache the factorization (using cholesky factorization)
[L U] = factor(A, a);  

for( k = 0; k < maxiter; k++) 
    {
         x^k+1 = (A^TA + a* I)^-1 (A^Tb + a (z^k - u^k))^T
    }

其中 A = mxn 矩阵和 n>>>m, b,u,z = nx1 向量，I = 单位矩阵和 a=0.001

Answer 1

这里计算量最大的操作是矩阵求逆，所以这取决于你如何实现这个操作。如果我们假设您使用 Gauss–Jordan 算法实现 takes O(n^3) 则整体复杂度为 O(maxiter * n^3)。在这里，我考虑到 n 大于 m(A^T*A 需要 O(m*n^2) )。

如果你在外面计算 (A^T*A + a*I)^-1 和 A^Tb 那么你就剩下

Inv * (Atb + a(z^k - u^k))^T

这是 O(n^2)，因为您需要将 nxn 矩阵乘以 nx1 向量，而加法和减法需要 O(n)。

不过，我在问题的评论中描述了尺寸上的一些不一致。