计算flops的数量

Question

对于下面的伪代码，我认为flops的数量是2n^3。但是，我不确定这是否正确，因为For循环让我怀疑它。(注意: aij和xij分别表示矩阵A和X的条目)

for ?=1:?
  for ?=1:?
    for ?=?:?
      ?=?+???*???    
    end
  end
end

Answer 1

这不是一个真正的matlab问题。这里有一种暴力的方法来解决它。

内部方程有两个flops，所以k循环有2(n-j+1) flops。

要完成剩下的工作，知道从1到p的q总和是p(p+1)/2，而从1到p的q^2总和是p(p+1)(2p+1)/6，这一点很有帮助。

j循环是针对j从1到i的2(n-j+1)，因此它具有2i(n+1)-i(i+1)=2i(n+1/2)-i^2 flops。

整个循环或i循环是2i(n+1/2)-i^2的总和，给出了n(n+1)(n+1/2) - n(n+1)(2n+1)/6 = n(n+1)(2n+1)/3。

您可以看到，这与从1到2i^2的n的总和相同。

检查这一点的一种方法，例如在matlab中，是设置一些n，并将f=0放在开头，并将内部方程替换为f=f+2;，然后结果将是f=n(n+1)(2n+1)/3。