【新人向け】計算量を意識してみよう

こんにちは、飯田です。
今回はアルゴリズムのカテゴリで記事を書かせていただこうと思います。

計算回数を考えてみよう
2重ループには気をつけよう
計算量の表し方〜ランダウの記号〜
ちなみに…
次回予告
参考記事

計算回数を考えてみよう

さて、早速ですが、以下の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() のような関数は、効率的なアルゴリズムが使われているはずです。たぶん…）

下の図に計算回数の増え方を表してみました。