矩阵乘法（分治法）.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.19M 资料格式：doc 举报版权申诉

byalias-6390517-16359647323861416364.doc.pdf-第1页.png

第1页 / 共7页

byalias-6390517-16359647323861416364.doc.pdf-第2页.png

第2页 / 共7页

byalias-6390517-16359647323861416364.doc.pdf-第3页.png

第3页 / 共7页

byalias-6390517-16359647323861416364.doc.pdf-第4页.png

第4页 / 共7页

byalias-6390517-16359647323861416364.doc.pdf-第5页.png

第5页 / 共7页

byalias-6390517-16359647323861416364.doc.pdf-第6页.png

第6页 / 共7页

byalias-6390517-16359647323861416364.doc.pdf-第7页.png

第7页 / 共7页

文本预览

矩阵乘法 1. 问题描述设 A 和 B 是两个 n*n 阶矩阵，求它们两的乘积矩阵 C。这里，假设 n 是 2 的幂次方。 2 2.1 问题分析 A 和 B 是两个 n*n 的矩阵，它们的乘积矩阵 C=AB 也是一个 n*n 矩阵，矩阵 C 中的元素 C[i][j]定义为 C[i][j]= ，则每计算一个 C[i][j]，需要做 n 次乘法和 n-1 次加法。因此计算 C 的 n2 个元素需要 n3 次乘法和 n3- n2 次加法。因此，所需的时间复杂度是 O(n3)。但是使用分治法可以改进算法的时间复杂度。这里，假设 n 是 2 的幂。将矩阵 A,B,C 中每一矩阵都分成 4 个大小相等的子矩阵，每个子矩阵是（n/2）*（n/2）的方阵。由此，可将方阵 C=AB 重写为因此可得： C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B22 C22=A21B12+A22B22 这样就将 2 个 n 阶矩阵的乘积变成计算 8 个 n/2 阶矩阵的乘积和 4 个 n/2 阶矩阵的加法。当 n=1 时，2 个 1 阶方阵的乘积可直接算出，只需要做一次乘法。当子矩阵阶 n>1 时，为求两个子矩阵的乘积，可继续对两个子矩阵分块，直到子矩阵的阶为 1。由此，便产生了分治降阶的递归算法。 2.2 复杂度分析时间复杂度：用于分块的函数 void matrixblock(int n,int **A,int **A11,int **A12,int **A21,int **A22)和用于合并的函数 void matrixunite(int n,int **A,int **A11,int **A12,int **A21,int **A22)的时间复杂度都是 O（n*n）。做两个矩阵相加的函数 void matrixadd(int n,int **A,int **B,int **C)的时间复杂度也是 O（n*n）。但是使用分治法将 2 个 n*n 矩阵的乘法划为做 8 个（n/2）*(n/2)矩阵的乘法和 4 个（n/2）*(n/2) 矩

阵的加法。所以整个算法的时间复杂度是。空间复杂度：程序中定义了一些整型变量和若干个二维数组。因此算法的时间复杂度是 O（n*n）。 3. 源代码 #include using namespace std; void matrixblock(int n,int **A,int **A11,int **A12,int **A21,int **A22) { } int i,j; int m=n/2; for(i=0;i

} } void matrixadd(int n,int **A,int **B,int **C) { } int i,j; for(i=0;i

B22=new int*[m]; C11=new int*[m]; C12=new int*[m]; C21=new int*[m]; C22=new int*[m]; C111=new int*[m]; C112=new int*[m]; C121=new int*[m]; C122=new int*[m]; C211=new int*[m]; C212=new int*[m]; C221=new int*[m]; C222=new int*[m]; int i; for(i=0;i

C211[i]=new int[m]; C212[i]=new int[m]; C221[i]=new int[m]; C222[i]=new int[m]; } matrixblock(n,A,A11,A12,A21,A22); matrixblock(n,B,B11,B12,B21,B22); matrixmul(m,A11,B11,C111); matrixmul(m,A12,B21,C112); matrixmul(m,A11,B12,C121); matrixmul(m,A12,B22,C122); matrixmul(m,A21,B11,C211); matrixmul(m,A22,B21,C212); matrixmul(m,A21,B12,C221); matrixmul(m,A22,B22,C222); matrixadd(m,C111,C112,C11); matrixadd(m,C121,C122,C12); matrixadd(m,C211,C212,C21); matrixadd(m,C221,C222,C22); matrixunite(n,C,C11,C12,C21,C22); } } int main(int argc, char** argv) { int n; cout<<"please input the number n:"<>n; int **A=new int*[n]; int **B=new int*[n];

int **C=new int*[n]; int i,j; for(i=0;i>A[i][j]; cout<<"please input the matrix B:"<>B[i][j]; matrixmul(n,A,B,C); cout<<"The matrix C which is the product of A and B is:"<

4. 运行结果 5. 心得体会运行时容易输错矩阵，从而造成结果不正确。

分享到：

赞收藏

资料库

矩阵乘法（分治法）.doc

相关推荐

课程资源

热门标签

最新资料