SxM*_*xMZ 2 algorithm math big-o matrix time-complexity
我已经研究了乘以两个n×n矩阵的大O复杂度,这需要时间O(n 3).但是,如何将两个矩形矩阵相乘得到大O复杂度,这两个矩阵的维数为m×n和n×r？我被告知答案是O(mnr),但我不确定这是从哪里来的.有谁能解释一下？
谢谢!
tem*_*def 12
我假设您正在讨论将两个维数为n×n的矩形矩阵乘以O(n 3)的复杂性,并且要求将m×n矩阵和n×r矩阵相乘的复杂性.有一些专门的算法可以比天真的方法更快地解决这个问题,但是出于这个问题的目的,我将简单地讨论标准"每行每列乘以每一行"算法.
首先,让我们看看O(n 3)项乘以两个n×n矩阵的位置.注意,对于所得矩阵的每个值,位置(i,j)处的条目由左矩阵的第i行和右矩阵的第j列的内积给出.每行和每列中有n个元素,因此计算每个元素需要时间Θ(n).这样做Θ(n 2)次(对于得到的矩阵的每个元素一次)需要时间Θ(n 3).
现在在m×n矩阵和n×r矩阵的乘积的背景下考虑这一点.矩阵中的条目(i,j)由左矩阵的第i行(其具有n个条目)和右矩阵的第j列(其具有n个条目)的内积给出,因此计算它需要时间Θ (N).您对结果矩阵的每个元素执行一次此操作.由于得到的矩阵具有维数m×r,因此需要考虑Θ(mr)个元素.因此,完成的总工作量是Θ(mnr).
希望这可以帮助!