エンジニアBLOG
h.iida
【新人向け】計算量を意識してみよう
こんにちは、h.iidaです。
今回はアルゴリズムのカテゴリで記事を書かせていただこうと思います。
計算回数を考えてみよう
さて、早速ですが、以下のPHPのコードはどちらが早く終了しそうでしょうか？
<?php
/**
* 1〜100000までの数字の中から、
* 2の倍数 かつ 3の倍数の数字を探す
*/
// コード①
for ($i = 1; $i <= 100000; $i++) {
// 2で割って余り0 かつ 3で割って余り0
if ($i % 2 === 0 && $i % 3 === 0) {
echo $i;
}
}
// コード②
for ($i = 1; $i <= 100000; $i++) {
// 2と3の倍数 = 6の倍数なので...
if ($i % 6 === 0) {
echo $i;
}
}おそらく答えは、②になるでしょう。
①と②で違うのは、if文の中の条件式のみです。
比較を行う回数はそれぞれ、
①は 100000 × 2回の比較 = 200000回
②は 100000 × 1回の比較 = 100000回
となります。
プログラムの処理で大きくコストがかかるのは演算や比較になるため、
計算の回数からこのように大まかな計算結果を見積もることができます。
例えば100までの数字から探すとなれば100回と200回の違いで済みますが、
100000回と200000回の違いは大きそうですよね。
2重ループには気をつけよう
以下のコードの計算回数は何回になるでしょうか？
<?php
for ($x = 1; $x <= 30; $x++) {
for ($y = 1; $y <= 30; $y++) {
echo $x + $y;
}
}
中に計算が1回あって、
・$x = 1, $y = 1 のときに1回
・$x = 1, $y = 2 のときに1回
...
・$x = 2, $y = 1
・$x = 2, $y = 2
...
・$x = 30, $y = 29
・$x = 30, $y = 30
というようにループしていくので、30 × 30 = 900回 の計算が行われることになります。
今回は30回ずつなので大したことはありませんが、10000回ずつだとどうでしょうか。
このときは、10000 × 10000 = 1億回となってしまいます。
このように、ループが何重かになっていると計算回数は指数関数的に増えていきます。
計算量の表し方 〜ランダウの記号〜
計算量を表す指標として、ランダウの記号 "O" を使う方法があります。
n 回の計算で済むのであれば、 O(n)、
2重ループで、各ループで n回 計算するとすると、 n の2乗回の計算になるので、O(n^2) と表します。
増え方はO(n^2)と比べてだいぶ小さいですね。
また、ただ実装するだけだとO(n^2)になってしまうような計算でも、
「アルゴリズム」を工夫すればO(n logn)のように、O(n^2)よりは小さいものにできたりもします。
計算量について調べるとよく紹介されているのは「ソート」に関するアルゴリズムですが、
ただ並び替えるだけでも、計算量を減らすための色々な方法があります。
（みなさんが普段使っている sort() のような関数は、効率的なアルゴリズムが使われているはずです。たぶん...）
下の図に計算回数の増え方を表してみました。
ちなみに...
ちなみに、コード①と②の計算量をランダウの記号を使って表すと、どちらも O(n) になります。
①の場合でも、nが増えることで爆発的に計算回数が増えるわけではないという意味です。
（社内で指摘をいただきました、ありがとうございます）
次回予告
今回は計算回数に着目して書いてきましたが、
次回は「メモリ」の消費について意識することの大切さについて書きたいと思います。
みなさんがより良いコードを書く上で助けになったら幸いです。
参考記事
もう少し込み入った内容が解説されている参考記事を貼っておきますので、
気になった方は是非読んでみてください。
C++入門 AtCoder Programming Guide for beginners (APG4b) - W - 2.06.計算量
