关于矩阵乘法的一个改进算法的时间复杂度

On the Complexity of an Improved Algorithm for Matrix Multiplications

中文关键词:  矩阵乘法  算法分析  比特运算次数  时间复杂度  计算数论

英文关键词:matrix multiplications  algorithm analysis  bit operations  time compiexity  computational number theory.

中文摘要:

      两个ｎ阶非负整数方阵相乘，常规算法的时间复杂度为Ｏ（ｎ^３），文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法，文献［２］对此算法做了进一步研究，提出三种改进策略．本文根据算法分析理论，得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ），因而其阶仍高于常规算法的运算量的阶．

英文摘要:

      The complexity of the conventional algorithm for multiplying two nn matrices ofnon--negative integers is O (n^３). Jiang and Wu [1] gave an "optimal" algorithm with O (n²)"operations". Later they [2] gave three ways to improve the algorithm. In this paper weconclude that the complexity of the improved algorithm is not yet lower than O (n^３logn), soits order is still higher than that of the conventional algorithm.