| 最值吸收算法解决矩阵连乘次序问题 |
| |
| 引用本文： | 赵雪岩,徐继明,陈景森.最值吸收算法解决矩阵连乘次序问题[J].西北纺织工学院学报,2013(6):827-830. |
| |
| 作者姓名： | 赵雪岩 徐继明 陈景森 |
| |
| 作者单位： | [1]空军工程大学信息与导航学院,陕西西安710077 [2]上海市电力公司崇明分公司,上海202150 |
| |
| 摘 要： | 通过分析矩阵序列乘法的特点，找到了一种新的算法一最小维数边界吸收算法，并将此算法分别与穷举搜索算法、动态规划算法的时间复杂度及空间复杂度进行分析比较．可以看出，动态规划算法的时间复杂度为O（n^3），空间复杂度为O（n^2），而本算法的时间复杂度和空间复杂度均为O（n），并且不需要额外的空间开销．
|
| 关 键 词： | 矩阵序列 维数数组 最小维数边缘化 最小维数吸收乘法 |
A minimum-absorption algorithm to solve-the problem of matrix multiply in succession |
| |
| ZHAO Xue-yan,XU Ji-ming,CHEN Jing-sen.A minimum-absorption algorithm to solve-the problem of matrix multiply in succession[J].Journal of Northwest Institute of Textile Science and Technology,2013(6):827-830. |
| |
| Authors: | ZHAO Xue-yan XU Ji-ming CHEN Jing-sen |
| |
| Affiliation: | 1. Telecommunication Engineering Institute, Airforce Engineering University, Xi＇an 710077, China 2. Chongming Branch of Shanghai Electric Company,Shanghai 202150 ,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | matrix sequence array of dimensions the least dimension marginalization the least dimen-sion absorb multiplication |
| 本文献已被 维普 等数据库收录！ |
