math - 合計と for ループ

Question

数式がたくさんある記事を読むのが苦手です。いくつかのスマトリーがあります (つまり、∑h ∑i のように) ネストされた 2 つの for ループとして記述できますか?

お気に入り：

for (h=1; h<=5; h++){
    for(i=1; i<=5; i++){
        sum+=i;
    }
}

お待ち頂きまして、ありがとうございます ：）

Answer 1

ここの例11を見ると：

 Sum(Sum(x*y)) = Sum(x)*Sum(y)

左辺は、ネストされた for ループとして記述できます。

for(x goes 1 to n)
  for(y goes 1 to m)
    add to the result (x*y)

右側は 2 つの独立したループとして記述できます。

for(x goes 1 to n)
  add to the firstResult (x)
for(y goes 1 to m)
  add to the secondResult (y)
set result to firstResult * secondResult

右側は O(n*m) 対 O(n+m) の時間効率を改善しますが、スペースがいくらかかかります (最初と 2 番目の結果を保持するため)。