前回、
・まず具体的な値で考えてみる
・結果を観察して、なにかの決まり事(法則性)を見つけだす
・決まり事を元に、n のときにどうなるか考えてみる
という話をしました。
これを「一般化」と言うと紹介しました。
プログラミングだけじゃなくて数学や物理でもよくつかう技法なので覚えてね。
この一般化を行う事で n がとても大きい値になったとしても プログラムの計算量を少なくすることができます。
計算量が少なくなるという事は、処理時間が短くなるということです。
その例を示したいと思います。
さて、ちょっと数学よりな話になってしまいますが、 合計を素早く計算できる「和の公式」というものがあります。
S = 1/2 * n * (n + 1)
まずこの公式がどうして導かれるのかを説明して、この公式を使って合計を求めるプログラムを書き直してみます。
まず合計は、
1 + 2 + 3 + ... n
と書けますね。もうすこし丁寧に書いてみます。
1 + 2 + 3 + ... (n - 2) + (n - 1) + n
n まで足すので途中を省略して書いていますが、 n の 1 つ手前は n - 1, n の 2 つ手前は n - 2 になるのはわかるかな?
この式を反対にして並べて書いてみます。 足し算なので交換則が使えます。
どんな順序で足しても、式を反対にしても結果は変わりません。足し算なので。
S = 1 + 2 + 3 + ... (n - 2) + (n - 1) + n S = n + (n - 1) + (n - 2) + ... 3 + 2 + 1
さて、ここで 2 つの式を眺めていると、何か見えてくることが無いかな?
2 つの式を足してみると、もっとよくわかるよ。
どうして反対にして足すのかを疑問に思うかも知れないけども、これはよくやる手法なんだよね。
反対にして足す、何か良いことあるかも? ぐらいの感じです。たぶん。
ネタバレ気味に言うと、反対にして足すと何か良いことが...
ありまぁす!
2S = (1 + n) + (2 + n - 1) + (3 + n - 2) + ..... + (n - 2 + 3) + (n - 1 + 2) + (n + 1)
左辺は S + S = 2S だね。
右辺は すべての項が n + 1 になるのわかるかな?
で、右辺は 1 から n まであったわけだから、n + 1 は n 個できるね。
n 個あるってことは、n 倍するってことと同じだね。
具体例で考えると、
7 * 3 = 21 7 + 7 + 7 = 21
掛け算って回数分足し算するって事と同じだからね。これは n でも同じだね。
これをまとめて式を整理すると
2S = n * (n + 1)
こうなる。
さてここで、求めたいのは S なので、
両辺を 2 で割ればいいね。
S = 1/2 * n * (n + 1)
はい、「和の公式」になりました。
ここまではいいかな?
と、長々と数学っぽい話をしてきましたが、 合計を計算するプログラムに話を戻します。
(define (sum-ex3 n)
(if (<= n 0)
0
(+ n (sum-ex3 (- n 1)))))このようにループして合計を求めていましたが、 ぶっちゃけループはいらなくて
(define (sum-ex4 n)
(/ (* n (+ n 1)) 2))和の公式でそのまま書けてしまいます。
人が普段使う式を、Scheme は前置記法なので変形しただけです。
実行してみよう。
gosh> (sum-ex4 100) 5050
和の公式を使うと何が良いのか、というと ループ処理をしないので計算量がものすごく少くなることです。
ためしに 100 億までの合計を求めてみよう。
gosh> (sum-ex4 10000000000) 50000000005000000000
和の公式を使ったプログラムは、一瞬で結果を表示しますが...
gosh> (sum-ex3 10000000000) ・・・・・・・・・・・・・・・・・
ループする従来のプログラムは、いつまで経っても結果を出力しません。*1
n が小さいうちは問題になりませんが、n を大きな値にすると問題になってしまうことがあります。
結論として和の公式を使ったプログラムのほうが優れていると言えるでしょう。
計算量のお話
計算量のことを「オーダー」と言い、「O(計算量)」みたいに表現します。
従来のループするプログラムは、n 回ループするので、
n に正比例して計算量が増えていきます。 これを「O(n)」と表現します。
和の公式を使ったプログラムは、ループしておらず n に関係なく計算量は一定です。 これを「O(1)」と表現します。
まとめると
O(1) ... n の値に関係なく計算量は一定。爆速!! O(n) ... n の増加に伴い計算量は線形的に増加する。まあ普通。 O(n^2) ... 指数関数的に計算量は増加する。やばめ。 O(n^3) ... 指数関数的に計算量はさらに激増する。かなりやばい。 O(n^4) 以降 ... 計算量が多すぎてちょっと使い物にならないです。プログラムの見直しが必要です。
となります。
「作ったプログラムがなかなか終了しない。」というときは、
計算量を少くするにはどうしたら良いか考えてみよう。
競技プログラミングやプログラミングサイトの問題では、
処理時間がかかりすぎると不正解になってしまう事もあるよ。
プログラムの計算量がどれぐらいなのか？や、
プログラムの処理速度を上げるにはどうしたらいいんだろう？
ってことも考えながらプログラムを書いてみよう！
つづく
*1:しばらく後にプログラムはメモリ不足に陥いり異常終了しました。実はループだけのせいじゃないんだけどコンピュータの内部事情は取り敢えず考えない事にします。
