帮我分析一下两种操作的计算成本

计算科学 matlab 算法 复杂 密集矩阵
2021-12-16 19:49:07

大家,我有一个关于算法计算成本的问题。那是:

我有两个向量,一个矩阵(可以是稀疏和密集)和标量系数,比我需要计算(由 Matlab 运行):un, vnCNACN×Nαn

(1)(其计算成本(主要是 CPU 时间)称为);yn=un+αnvnK

(2) 矩阵-向量积:(其计算成本(主要是 CPU 时间)称为)。zn=AunL

所以我想知道我们有:

1) ??5K>L

2) ??5K<L

1)-2) 的假设是否合理?我想收到一些关于这个问题的评论。

1个回答

让稀疏矩阵的一行中稀疏条目的平均数为那么矩阵向量乘积 ( ) 的复杂度大约为Nszn=AunO(NNs)

的复杂度为了第二个成立yn=un+αnvnO(2N)

5K<L,我们需要 <5(2N)NNs

因此,如果,即第二个条件成立。Ns>10