摘要
两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n^3),文献[1]提出一个“运算次数”为O(n^2)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n^3log_2~n),因而比常规算法的运算量还大.
The complexity of the conventional algorithm for multiplying two n * n matrices of non-negative integers is O(n^3). Jiang and Wu [1] give an 'optimal' algorithm with O(n^2) 'operations '. In this paper we conclude that the complexity of this algorithm is not lower than O(n^3log_2 n), so it is worse than the conventional algorithm.
