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

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

宋晓艳

【期刊名称】《科技传播》 【年(卷),期】2010(000)023

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

【关键词】矩阵乘法;凝聚算法;算法复杂度;对数代价 【作者】宋晓艳

【作者单位】同济大学电子与信息工程学院,上海,201804 【正文语种】中文 【中图分类】O1 【相关文献】

1.关于矩阵乘法的一个改进算法的时间复杂度 [J], 张振祥 2.关于矩阵乘法的一个算法的时间复杂度 [J], 张振祥 3.程序设计算法的选择与时间复杂度的计算 [J], 刘录英

4.常用算法时间复杂度的计算方法 [J], 殷超

5.平均计算时间复杂度优化的动态粒子群优化算法 [J], 王沁; 李磊; 陆成勇; 孙富明

以上内容为文献基本信息，获取文献全文请下载