网站建设流程 费用,你们交学费做网站,有含义的公司名,东莞网站建设咨询公矩阵乘法的Strassen这个算法就是在矩阵乘法中采用分治法#xff0c;能够有效的提高算法的效率。先来看看咱们在高等代数中学的普通矩阵的乘法两个矩阵相乘上边这种普通求解方法的复杂度为: O(n3)也称之为暴力求解或者朴素求解这是暴力求解的代码#xff0c;三重循环#xff…矩阵乘法的Strassen这个算法就是在矩阵乘法中采用分治法能够有效的提高算法的效率。先来看看咱们在高等代数中学的普通矩阵的乘法两个矩阵相乘上边这种普通求解方法的复杂度为: O(n3)也称之为暴力求解或者朴素求解这是暴力求解的代码三重循环显然复杂度是O(n3)、voidMul(int** matrixA,int** matrixB,int** matrixC){for(inti 0; i 2; i){for(intj 0; j 2; j){matrixC[i][j] 0;for(intk 0; k 2; k){matrixC[i][j] matrixA[i][k] * matrixB[k][j];}}}、由于不满足上边这种复杂度太大德国某位牛人开始找另外的解法了先分析一下下边的将一个矩阵分成四块如上图A和B矩阵都被分成了四块该算法复杂度依然是n3于是上边那位老哥不服他觉得这不是最优的解还有更优的于是他分析了上边是四个等式四个等式中有八个乘法四个加法矩阵乘法的复杂度主要就是体现在相乘上而多一两次的加法并不会让复杂度上升太多。故此老哥思考是否可以让矩阵乘法的运算过程中乘法的运算次数减少从而达到降低矩阵乘法的复杂度我们都知道想要获取时间上的效率很多时候都是以空间换时间于是老哥定义了七个变量这七个变量均是矩阵ABCDEFGH原来两个相乘矩阵里边划分好的八个小矩阵图三或者看这个图总之七个矩阵变量是要求的(PPT上和这差不多只是变量顺序换了)图四求出则七个矩阵就能求出A*B的值这个图就是A*B的值至于为什么能求出来归功于牛人构造的七个巧妙的式子利用七个式子之间的关系就求出了下边四个变量也就是解图五最后那老哥证明了这个复杂度是这个图六顺带复习一下PPT上这个如对于上边图六那个公式a7,k2,b2 显然72^2,所以套第三个T(n)动态规划算法动态规划和分治法相似都是通过组合字问题来求解原问题不同之处在于分治法的子问题互不干涉、互不交叉而动态规划相反它会利用已经求解的子问题进而求解新的子问题先举个简单的例子感受一蛤什么是动态规划钱币问题——用面值1元、3元、5元的硬币如何用最少的硬币凑到11块钱第一步要想的就是怎么把一个大问题变小问题既然要求最少的硬币凑到11块钱这里用c[i]表示凑到i元最小要j个硬币那我先求最少的硬币凑到0块钱显然需要0个硬币所以才c[0]0接下来求最少的硬币凑到1块钱现在只有面值1块的能用我就用一个用完之后还需凑0元这时才c[0]0已知所以才c[1]1c[0]1接下来求最少的硬币凑到2块钱现在只有面值1块的能用我也先用一个用完之后还需凑1元这时才c[1]1已知,所以c[2]1c[1]2接下来求最少的硬币凑到3块钱现在有面值1块的和三块的如果我先用一个3块的用完之后还需凑0元这时才c[0]0已知,所以c[3]1c[0]1如果我先用一个1块的用完之后还需凑2元这时才c[2]2已知,所以c[3]1c[2]3取这两种中的最小的那种情况后边的以此类推....矩阵链乘法如果要求n个给定序列的矩阵相乘的乘积(比如ABCDEFG)矩阵具有结合律所以计算的步骤有很多种选择但如果结合律用的不好会产生比较大的代价在了解这个咱们要研究算法是干啥的之前先了解几个概念1、矩阵相容也就是两个矩阵要能够相乘即A的列数等于B的行数2、标量乘法若A是p*q,B是 q*r则A*B的代价就是其标量乘法也就是pqr所以要求n个给定序列的矩阵相乘的乘积我们要研究使得该成绩代价最小也就是其标量乘法次数之和最少(这块最好参照一下算法导论211页很详细)说白了就是在乘法式子中如何打括号官方的话就不说了直接上一串矩阵你应该干什么和怎么干哈哈怎么干图中给出了6个矩阵相乘你应该做的就是给它大括号决定计算顺序使得计算代价最小这个就是m[ ][ ]的算法 int t m[i][k] m[k1][j]p[i-1]*p[k]*p[j] 、现在来解释一下上边的这个算法我只能说老师的PPT略傻逼都没怎么解释m[i][j]表示矩阵从第i个矩阵乘到第j个矩阵的最小代价int t m[i][k] m[k1][j]p[i-1]*p[k]*p[j] 上边这个算法的意思是第i个矩阵到第k个矩阵相乘的代价第k个矩阵到第j个矩阵相乘的代价加上这两个乘好了的前后两个矩阵相乘的代价然后理解了怎么算从小到大算就OK了按照斜线的顺序算i和j挨着越近越好算先算对角线全是0再算m[1][2],m[2][3],m[3][4]...以此类推因为后边计算的斜线会用到上一条斜线上那些数比如算m[1][3]会用到m[1][1],m[1][2],m[2][3],m[3][3]最后解释一下怎么找分解点也就是在哪打括号下边图的矩阵是标记矩阵也就是在动态规划的过程中你每次的最优解是在哪划分的它会记录下来如果要求A[1][6]怎么打括号找到s[1][6]3,然后在A[1][3]和A[3][6]里重复上边的步骤每个找到的点都是分界点..比如第一个找到的3【6】】来自moonsmile的祝福~明天将推出贪心算法
