矩阵加法的复杂度是多少? [英] What is the complexity of matrix addition?

问题描述

我发现关于矩阵加法的另一个问题是二次运算，有一些提及一个>.但是我认为它是线性的.

I have found some mentions in another question of matrix addition being a quadratic operation. But I think it is linear.

如果我将矩阵的大小加倍，则需要计算加法的两倍，而不是四倍.

If I double the size of a matrix, I need to calculate double the additions, not quadruple.

主要分歧点似乎是问题的规模.对我来说，这是矩阵中元素的数量.其他人则认为这是列数或行数，因此O(n^2)复杂度.

The main diverging point seems to be what is the size of the problem. To me, it's the number of elements in the matrix. Others think it is the number of columns or lines, hence the O(n^2) complexity.

我将其视为二次运算遇到的另一个问题是，这意味着将3维矩阵加为三次方，而将4维矩阵加为O(n^4)等，即使所有这些问题都可以简化为两个向量相加的问题，它具有明显的线性解.

Another problem I have with seeing it as a quadratic operation is that that means adding 3-dimensional matrices is cubic, and adding 4-dimensional matrices is O(n^4), etc, even though all of these problems can be reduced to the problem of adding two vectors, which has an obviously linear solution.

我是对还是错?如果错了，为什么?

Am I right or wrong? If wrong, why?

推荐答案

这取决于您对问题大小的定义:是元素总数还是矩阵的宽度/高度.哪一个是正确的实际上取决于矩阵加法其中一部分的较大问题.

As you already noted, it depends on your definition of the problem size: is it the total number of elements, or the width/height of the matrix. Which ever is correct actually depends on the larger problem of which the matrix addition is part of.

NB:在某些硬件(GPU，矢量机等)上，添加可能会比预期运行得更快(即使复杂度仍然相同，请参见下面的讨论)，因为硬件可以一步执行多次添加.对于有限的问题大小(例如n <3)，它甚至可能只是一步.

这篇关于矩阵加法的复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！