实验八作业
实验八
1、问题
“矩阵链乘法，特别要求举例时采用不同于讲义的数据进行推导。”
2、解析
设A1,A2,A3,…,An为n个矩阵的序列，其中Ai为Pi-1×Pi阶矩阵，这个矩阵链的输入用向量P=
给定向量 P，确定一种乘法次序，使得基本运算的总次数达到最小。
例如，P=<2,4,6,8>,A1:2×4,A2:4×6,A3:6×8
1)(A1A2)A3=246+268
2)A1(A2A3)=248+468
Ai…j:表示矩阵链相乘的子问题Ai，Ai+1…Aj； M[i…j]:表示得到乘积Ai…j所用的最少基本运算次数；假设，最后一次相乘发生在矩阵链Ai…k和Ak+1…j之间，即
3、设计
4、分析
时间复杂度：O(n3)
5.源码
https://github.com/land555/algorithm-analy-sis/blob/main/week8.cpp
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！