张振祥.关于矩阵乘法的一个算法的时间复杂度[J].数学研究及应用,1992,12(3):473~475
关于矩阵乘法的一个算法的时间复杂度
On the Complexity of an Algorithm for Matrix Multiplications
投稿时间:1990-08-11  
DOI:10.3770/j.issn:1000-341X.1992.03.027
中文关键词:  
英文关键词:
基金项目:
作者单位
张振祥 安徽师范大学数学系
中国科大研究生院信息安全国家重点实验室 
摘要点击次数: 2148
全文下载次数: 1932
中文摘要:
      两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n3),文献[1]提出一个“运算次数”为O(n2)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n3log2n),因而比常规算法的运算量还大.
英文摘要:
      The complexity of the conventional algorithm for multiplying two n * n matrices of non-negative integers is O(n3). Jiang and Wu [1] give an "optimal" algorithm with O(n2) "operations ". In this paper we conclude that the complexity of this algorithm is not lower than O(n3log2n), so it is worse than the conventional algorithm.
查看全文  查看/发表评论  下载PDF阅读器