矩阵乘法复杂度分析 |
您所在的位置:网站首页 › 空间复杂度和时间复杂度怎么算 › 矩阵乘法复杂度分析 |
一 背景
在很多机器学习或者数据挖掘论文中,里面或多或少的涉及到算法复杂度分析。进一步思考,是如何得到的呢? 很长时间里,我也感受到比较疑惑,阅读论文过程中,在涉及到这部分内容时,会直接跳过算法复杂度分析这快。 其一是因为比较烧脑。虽然知道复杂度分析是对算法总体上的概况,用来进行算法间好坏的比较(由此可见,重要性)。 其二是算法分析基础比较薄弱(个人主观上也是不想的)。 算法复杂度在《数据结构》课程中也或多或少的涉猎,说完全不知道属于自己骗自己,简单的一些例子还是会分析的,但当涉及到复杂的目标方程是,特别是含矩阵运算,就不知道如何分析了。也没有领路人,不知道如何下手。随着看的论文数量上升,慢慢摸索过程中突然就通了,知道如何去分析了。写这篇博客的目的希望读者能够明白如何对矩阵乘法进行复杂度分析,少走一些弯路。笔者先介绍2个矩阵相乘复杂度,然后介绍3个矩阵相乘复杂度,最后介绍几篇论文里面的loss方程,如何运用矩阵乘法复杂度去分析算法的好坏。 需要的基础,初步了解《数据结构》第一章知识,至少知道算法复杂度是什么以及如何表示。 什么是矩阵乘法?(熟悉同学可以跳过) 矩阵乘法:矩阵乘法(英语:matrix multiplication)是一种根据两个矩阵得到第三个矩阵的二元运算,第三个矩阵即前两者的乘积,称为矩阵积 二元运算:需要2个对象参与,这里指2个矩阵。 条件:它只有在第一个矩阵的列数(column)和第二个矩阵的行数(row)相同时才有意义 二 矩阵乘法对于矩阵A(n*m),B(m*n), 这里A(n*m)表示A是n行乘m列的矩阵。 如果A*B,那么复杂度为O(n*m*n),即O(n^2m) 。进一步思考,为什么呢,直接代码解释: for(i=0;i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |