the art of computer programming 1.2.3 を読む
1.2.3 総和と乗積
式(13)について
この式の左辺の計算量はで、右辺はである。
この2つの計算量の違いは大きく、左辺はで、1億回の計算することになる(実際は5千万回ほど)。
しかし、左辺は同じでも計算回数は1万回(実際は1万回の計算が2回あるので2万回の計算が必要)で終わる。
演習問題
6.[HM20]
ベン図で考えれば以下の式が導き出せる。
上の4つの式は左辺、つまり3つの総和が分かれば右辺の1つの総和がわかることを表している。