プログラムを実行するとき、その良し悪しはどのように判断できるのだろうか？
まず、そもそもの大前提として「やりたいことができる」ことだろう。これができないと組んだ意味がなくなってしまう。
これは機能要件と言ったりする。文字通り、機能としてこれは欲しいよというものが定義されているのだ。
では、それができた次の段階。今度は、その性能が重要になってくる。
こちらは、非機能要件だ。こちらも文字通り、機能以外で、こういう部分は満たさなきゃいけない、というものだ。
その非機能要件の中でも、今回はその処理にかかる時間を見ていこう。
計算量、というやつだ。
前回と今回のお話
前回は、「アルゴリズムとデータ構造」とは何か、という部分を解説した。
とりあえず大雑把に「そんなもんなんだな」程度で分かってもらえれば十分だ。
で、今回はこのアルゴリズムの性能を評価するための指標として、計算量というものに触れていく。
数式とかが出てくるが、それについても補足を入れていこう。
計算量
計算量とは？
まずは言葉の定義から。
計算量とは、入力されたデータ数\(n\)によって、その処理を行うためにどの程度の時間が必要かを表す尺度だ。
これは厳密な計算回数を見るのではなく、\(n\)の大きさで、大まかに表現したものになる。
具体例を見てみよう。前回アルゴリズムの説明で出した二つのJavaScript関数を再掲する。
function sumAll1(num){
var res = 0;
for(var i = 1; i <= num; i++){
res += i;
}
return res;
}function sumAll2(num){
return n * (n + 1) / 2;
}これら二つの関数で、具体的に計算量を見てみよう。
なお、考えるにあたって、両方とも1からnumまでの数字を入力している、と考えてみる。
まず一つ目のsumAll1関数。見てもらってわかる通り、入力となる数全部を一つずつ足している。
つまり、この入力数が一つ増えると、以下3つの計算が一回ずつ増える。
iとnumを比較するresにiを加算するiを1増やす
つまり、入力numが大きくなるにつれて、計算時間も一次関数的に増加していく。
では、二つ目はどうか。同じ入力なのに、numがどんな数字だろうと一回の計算で完了している。
ということは、入力のデータ数に関係なく、一定の計算時間で完了できるのだ。
この結果を見ると、二つ目に出した例の方が優れている、ということが分かるだろう。
この、計算時間を一定の書き表し方をしたものが、計算量になる。
計算量は、入力のデータ数を\(n\)とした場合に、\(O(n\)の関数\()\)と書く。読み方は、オーダー○○。
なぜこれを考えるかだが、複数のアルゴリズムで計算にかかる時間を比較するためだ。
計算量の考え方
計算量は、大雑把な精度で表現を行う。
細かい数値を出して比較しても、結局それを実行するPCの性能などに左右されてしまい、意味がないからだ。
だから、入力されたデータ数\(n\)に対して、どれだけ計算回数が大きくなるかにのみ着目する。
例えば、上のsumAll1関数。これは、以下の計算を行っている。
resに0を代入で1回iに0を代入で1回iとnumを比較でn + 1回resへのiの加算でn回iのインクリメントでn回resの出力で1回
これを全部足すと、\(3n + 4\)回だ。例えば、入力が2なら、全部で10回の計算を行っていることになる。入力が100なら、304回。
しかし、計算量で表すと、\(O(n)\)となる。大雑把だろう。とはいえ、この大雑把にするのにも考え方がある。
まず、定数を足したり、定数倍するのは無視する。つまり、\(n\)回の計算も、\(100n+5000\)回の計算も、計算量の考え方では同じ\(O(n)\)だ。
次に、計算量同士の足し算を考える。二つの\(n\)の関数\(f(n)\)と\(g(n)\)の計算量の足し算は、この大きい方の計算量になる。
\(n\)が十分に大きくなれば、その差は無視できる、という考え方だ。
で、よく使われるものとしては以下のものが挙げられる。左の方が計算量が少なく、右に行く方が多い。
$$1, \log(n), n, n\log(n), n^2, n^3, …, n^k, 2^n$$
最後に、計算量同士の掛け算だ。
これは、純粋にその掛け算の結果をそのまま書く。
例えば、\(n\)回の処理で、その1回ごとにさらに\(n\)回の処理を行っていたとした場合は、計算量は\(O(n) * O(n) = O(n^2)\)だ。
状況によって…
計算量は、状況によって変化する場合がある。
例えば、配列の中からあるデータが存在するかどうかを探索する場合を考えてみよう。
具体的には、以下のような関数だ。
配列arrと、その中から探したいデータdataを入力して、そのデータが入っている添え字を返すとしている。また、見つからなかったら-1を返す。
function findData(arr, data) {
for(var i = 0; i < arr.length; i++){
if(arr[i] == data){
return i;
}
}
return -1;
}この関数の場合、一番計算回数が少ないのは、先頭にデータが入っていた場合。
一回の比較で終了しているので、この計算量は\(O(1)\)だ。一瞬で終わる。
で、最悪の場合を考えると、データが一番最後、あるいはそもそも入っていなかった場合。
比較を\(n\)回行っていて、最悪計算量は\(O(n)\)だ。データ量がとんでもないことになっていたら、そこそこ時間がかかる。
そのどっちを見るかという話だが、通常は最悪計算量を見る。
最悪でもこれだけあれば終わるよ、というもので比較を行うのだ。
でも、それだけでも不十分な場合がある。後で解説するクイックソートというやつが一例なのだが、最悪計算量が\(O(n^2)\)なのに対し、平均計算量は\(O(n\log(n))\)なのだ。
ちょっとアルゴリズムの中で工夫をしており、ふつうは常に平均計算量で処理を行える。その場合は、平均計算量で考える。
具体例を今出すのが難しいので、「例外としてそういうやつがいるんだな」と思っておいてくれればいい。詳細は、そのクイックソートとやらを解説するときに譲ろう。
補足：対数について
さて、上の計算量の実例で\(\log(n)\)というやつが出てきている。
これは対数というやつなのだが、高校で苦手だったという人も多いと思う。
なので、改めてこの対数についても解説しておこう。ここからはいったんプログラムから離れて、数学の話に入る。
対数の定義
対数の定義は、以下の通りだ。
\(a = b^c\)のとき、\(c = \log_b(a)\) ただし、\(b \not = 1\)
言葉でも説明しておこう。
ある1以外の数\(b\)を\(c\)乗したら、\(a\)になる。それを表しているのが、上の左側、指数だ。
それに対し、対数は、ある数\(b\)を\(a\)にするためには何乗すればいいのか、というものを表したものだ。
上の数式で言えば、\(b\)を\(a\)にするためには、\(c\)乗すればいい、となる。
このように、実質は指数と対数は同じ関係を表している。どこの部分を表しているかが異なる。
累乗した結果が指数、何回掛ければいいかが対数だ。
なお、\(c = \log_b(a)\)と書いたとき、\(b\)を底と呼ぶ。
対数の計算
計算法則も出しておこう。
- 対数の加算
\(\log_c(a) + \log_c(b) = \log_c(ab)\) - 対数の減算
\(\displaystyle \log_c(a) – \log_c(b) = \log_c(\frac{a}{b})\) - 対数の定数倍
\(b\log_c(a) = \log_c(a^b)\) - 性質
\(\log_a(a) = 1\)
やる気のある人は、証明にチャレンジしてみよう。
計算量における底
さて、一つお気づきだろうか。
計算量の部分で出した対数には、底がない。これは省略されているのだ。
基本的に、計算量として使う対数の底は2と決められている。
だから、毎回2を書くのが面倒なので、省略されている、というわけだ。
まとめ
ちょっと短い気もするが、このあたりはスピードを無理に上げて理解が疎かになってもいけない。ゆっくり行こう。
今回は、計算量とは何かと、その計算方法を解説した。オマケで対数も。
計算量に関するまとめを以下に書いておこう。
- 計算量とは：
データ数\(n\)に対する大雑把な計算時間 - 計算量の計算方法：
- 定数倍、定数の加算は無視する
- 計算量同士の加算は大きい方を結果とする
\(O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))\) - 計算量同士の乗算は、そのまま計算する
\(O(f(n)) * O(g(n)) = O(f(n) * g(n))\)
- 計算量の大小(小→大)
\(1, \log(n), n, n\log(n), n^2, n^3, …, n^k, 2^n\)
具体例がちょっと少なかったが、今後解説する各アルゴリズムでも、この計算量を出してみようと思う。
そちらも見ながら感覚を掴んでいこう。
更新情報はTwitterでも呟いている。よかったらページ下部のTwitterアイコンから覗いていってほしい。
それでは。
コメント