【数学】矩阵乘法、计算协方差矩阵的时间复杂度

(1)矩阵乘法

A(n,m)*B(m,n)=C(n*n)

遍历矩阵C用到两轮循环:遍历n行、每行n个元素;

矩阵C中的每个元素计算,都是是A的一行乘以B的一列,用到一轮循环:m个元素;

所以时间复杂度是n*n*m

 

(2)矩阵的协方差矩阵

向量的协方差,表示两个向量元素之间的相关性,计算公式为:

【数学】矩阵乘法、计算协方差矩阵的时间复杂度

 矩阵的协方差,本质上也是向量运算:

【数学】矩阵乘法、计算协方差矩阵的时间复杂度

计算协方差矩阵的时间复杂度:

(1)不要把这里的X看作矩阵,而是看作多个列向量c1,c2,..., cn的组合,每个列向量中有m个元素;

(2)矩阵的协方差就是求这些列向量之间的相关性,按第一幅图中的公式,两个列向量的协方差需要1轮循环:m次计算;

(3)遍历最终的协方差矩阵需要两轮循环:遍历n行,每行n个元素;

最终的时间复杂度为n*n*m,和矩阵运算的时间复杂度一样。