计算翻牌的次数

Question

对于下面的伪代码；我认为翻牌的数量是 2n^3。但是，我不确定这是正确的，因为 for 循环让我怀疑它。（注：aij和xij分别代表矩阵A和X的条目）

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

Answer 1

这不是真正的 matlab 问题。这是一种蛮力解决方法。

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

要完成剩下的工作，知道从 1 到 p 的 q 的总和是 p(p+1)/2 和从 [=13 的 q^2 =] 到 p 是 p(p+1)(2p+1)/6.

j 循环是 2(n-j+1) for j 从 1 到 i，所以它有 2i(n+1)-i(i+1)=2i(n+1/2)-i^2 个失败。

总体或 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。

可以看到这和2i^2的1到n的和是一样的。

一种检查方法，例如在matlab中，就是设置一些n，然后把f=0放在开头，用f=f+2;代替里面的方程，那么结果就是f=n(n+1)(2n+1)/3.

Counting the number of flops