最值吸收算法解决矩阵连乘次序问题  

A minimum-absorption algorithm to solve the problem of matrix multiply in succession

作　　者：赵雪岩[1] 徐继明[1] 陈景森[2] 

机构地区：[1]空军工程大学信息与导航学院,陕西西安710077 [2]上海市电力公司崇明分公司,上海202150

出　　处：《西安工程大学学报》2013年第6期827-830,共4页Journal of Xi’an Polytechnic University

摘　　要：通过分析矩阵序列乘法的特点,找到了一种新的算法—最小维数边界吸收算法,并将此算法分别与穷举搜索算法、动态规划算法的时间复杂度及空间复杂度进行分析比较.可以看出,动态规划算法的时间复杂度为O(n3),空间复杂度为O(n2),而本算法的时间复杂度和空间复杂度均为O(n),并且不需要额外的空间开销.According to the characteristics of matrix multiply in succession, a new algorithm--the least dimension boundary absorb algorithm was found. In addition, the space and time complexity of the ex- haustive search algorithm and the dynamic programming algorithm were compared with the new algo- rithm. The results show that the time complexity of the dynamic programming algorithm is O（na） and the space complexity is O（n2） ,while the space and time complexity of the new algorithrn are both O（n）, whatrs more, the algorithm does not need the extra storage space.

关 键 词：矩阵序列 维数数组 最小维数边缘化 最小维数吸收乘法 

分 类 号：O241.6[理学—计算数学]