the art of computer programming 1.2.3 を読む

1.2.3 総和と乗積

式(13)について

    \sum_{i=0}^n\sum_{j=0}^ia_ia_j=\frac{1}{2}((\sum_{i=0}^na_i)^2+(\sum_{i=0}^na_i^2) )

    この式の左辺の計算量はO(n^2)で、右辺はO(n)である。

    この2つの計算量の違いは大きく、左辺はn=10000で、1億回の計算することになる(実際は5千万回ほど)。

    しかし、左辺は同じn=10000でも計算回数は1万回(実際は1万回の計算が2回あるので2万回の計算が必要)で終わる。

 

演習問題

6.[HM20]

    ベン図で考えれば以下の式が導き出せる。

    \sum_{S(j)}a_j+\sum_{R(j)andS(j)}a_j-\sum_{R(j)orS(j)}a_j=\sum_{R(j)}a_j

    \sum_{R(j)}a_j+\sum_{R(j)andS(j)}a_j-\sum_{R(j)orS(j)}a_j=\sum_{S(j)}a_j

    \sum_{R(j)}a_j+\sum_{S(j)}a_j-\sum_{R(j)andS(j)}a_j=\sum_{R(j)orS(j)}a_j

    \sum_{R(j)}a_j+\sum_{S(j)}a_j-\sum_{R(j)orS(j)}a_j=\sum_{R(j)andS(j)}a_j

    上の4つの式は左辺、つまり3つの総和が分かれば右辺の1つの総和がわかることを表している。