矩阵乘法的凝聚算法时间复杂度计算

矩阵乘法的凝聚算法采用"先合后分"的思想,先将矩阵变换为非负整数矩阵,再将矩阵间的乘积转化为向量和矩阵的乘积,而后根据整数的带余除法定理进行辗转相除后再利用适当变换即可得到原矩阵乘积。鉴于该算法的时间复杂度问题存在争议,本文对于该问题作了深入探讨,用算法复杂度的统一代价标准尤其针对对数代价标准计算了凝聚算法的时间复杂度,从而可以在两种计算复杂度的标准下将凝聚算法与其他矩阵乘法的算法进行时间复杂度比较。结果,在统一标准下,凝聚算法能够达到矩阵乘法算法复杂度的最低下界;而在对数代价标准下,凝聚算法其复杂度虽不优于也并不远远高于其它矩阵乘积算法复杂度。