むにえる牧場

毎日むにえるをつくっています

学生時代の数学って大事だなと思った話

概要

とある企業の面接にてソートアルゴリズム、もとい計算量の求め方をそらで説明できるかと言われ、「やべえ……できねえ……」となってしまったので、改めて勉強し直してました。
勉強用に使っている本はこちら

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

本の中で、まっさきにバブルソートの紹介がされ、計算量の求め方も紹介されるのですが、そこでの途中式が理解できませんでした……。

※Cを1回の処理にかかる計算量として
CN+(N-1)C+(N-2)+・・・+C(2)+C(1)
=C \displaystyle \frac {1}{2}N(N-1)
↑これの  \displaystyle \frac {1}{2} がどこから出てくるのかわかってなかった。

よく考えてみると数列の公式を使ったもので、「学生時代の数学って……大事だな……」と身に染みたので備忘録。

1からnまでの和を求める公式

1+2+3+・・・+n
という数式があった場合、
 \displaystyle \frac {1}{2}n(n+1)
となります。

なぜこの数式になるのか、具体的な数字を入れて考えてみます。
仮にn=10だとすると、 x=1+2+3+4+5+6+7+8+9+10 になります。

ここで同じ式を逆順で並べると、
x=1+2+3+4+5+6+7+8+9+10
x=10+9+8+7+6+5+4+3+2+1
この2つの式をまとめると、
2x=(1+10)+(2+9)+(3+8)+(4+7)+(5+6)+(6+5)+(7+4)+(8+3)+(9+2)+(10+1)
2x=(11)×10
x=(11×10)÷2
になります。

同様の手順をnのまま進めれば、
x=1+2+3+・・・+(n-2)+(n-1)+n
x=n+(n-1)+(n-2)+・・・3+2+1
この2つの式をまとめて、
2x=(1+n)+(2+(n-1))+(3+(n-2))+・・・((n-2)+3)+((n-1)+2)+(n+1)
2x=(n+1)+(n+1)+(n+1)・・・(n+1)+(n+1)+(n+1)
(n+1)がn個あるので、
2x=n(n+1)
x= \displaystyle \frac {1}{2}n(n+1)

公式が導けました。
 \displaystyle \frac {1}{2}もどこから出てきたか理解できました。

まとめ

学生時代の勉強は大事だと改めて痛感した瞬間でした……。
完全に自分のための備忘録記事です。
ただ一度文章化すれば見直せるし、頭にもインプットしやすいので、役に立つはず。たぶん。