【数学】矩阵乘法、计算协方差矩阵的时间复杂度
(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,和矩阵运算的时间复杂度一样。