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

On the Complexity of an Algorithm for Matrix Multiplications

中文摘要:

      两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.

英文摘要:

      The complexity of the conventional algorithm for multiplying two n * n matrices of non-negative integers is O(n³). Jiang and Wu [1] give an "optimal" algorithm with O(n²) "operations ". In this paper we conclude that the complexity of this algorithm is not lower than O(n³log₂n), so it is worse than the conventional algorithm.