大家,我有一个关于算法计算成本的问题。那是:
我有两个向量,一个矩阵(可以是稀疏和密集)和标量系数,比我需要计算(由 Matlab 运行):
(1)(其计算成本(主要是 CPU 时间)称为);
(2) 矩阵-向量积:(其计算成本(主要是 CPU 时间)称为)。
所以我想知道我们有:
1) ??
2) ??
1)-2) 的假设是否合理?我想收到一些关于这个问题的评论。
大家,我有一个关于算法计算成本的问题。那是:
我有两个向量,一个矩阵(可以是稀疏和密集)和标量系数,比我需要计算(由 Matlab 运行):
(1)(其计算成本(主要是 CPU 时间)称为);
(2) 矩阵-向量积:(其计算成本(主要是 CPU 时间)称为)。
所以我想知道我们有:
1) ??
2) ??
1)-2) 的假设是否合理?我想收到一些关于这个问题的评论。
让稀疏矩阵的一行中稀疏条目的平均数为。那么矩阵向量乘积 ( ) 的复杂度大约为。
的复杂度为。为了第二个成立
,我们需要 <
因此,如果,即第二个条件成立。