プログラムの計算量とは？オーダー記法など基本的なことまとめ

はじめに

この記事は ミライトデザイン Advent Calendar 2021 の 15日目の記事となっています。

前回は「競技プログラミングをしなくても知っておきたい計算量のはなし」という記事を書いてくれた ほげさん でした。

今回の記事はそれに続いて、そもそも計算量とはなんですか？といった人向けに、というか自分の整理用にざっくりとまとめてみようと書き始めた記事となっています。

計算量についてあまりわからないという人は、この記事を読んだ後にもう一度 ほげさんの記事を読んでみると面白いと思います。

計算量とは？

そもそも、計算量とは何？って人はいないでしょうか。

正直アドカレで計算量について書こうと決まるまで、自分はよく分かってなかったです。

で、計算量とは何かをざっくり説明すると、プログラムの計算効率はどのぐらいなのかを測る指標のようなものです。

プログラムの処理には計算や、繰り返し、比較などの様々な処理がありますが、これらの処理はデータ（要素）がどれぐらい増えたらどれぐらいの割合で実行時間が増えていくのかを表したりします。

計算量には大きく
プログラムが処理を実行する際にどれぐらいの「手順」を必要とするのかを指標とするものと、
プログラムが処理を実行する際にどれぐらいの「メモリ」を必要とするのかを指標とするものの2種類があります。

これらの指標を使って、より効率的なアルゴリズムを測ったりします。

時間計算量

時間計算量は先述の通り「プログラムが処理を実行する際にどのぐらいの手順を必要とするのか」を表す指標です。

1万回の処理が実行されるより、1回の処理が実行される方が短い時間で実行できますよね。

そういった処理の手順回数（ステップ数）を比較して、より短い時間で実行できる効率のよいアルゴリズムを測ることができます。

空間計算量

空間計算量も先述の通り「プログラムが処理を実行する際にどのぐらいのメモリを必要とするのか」を表す指標です。

時間計算量の手順回数とは違い、空間計算量はプログラムの実行に必要なメモリを表します。

最近ではパソコンのメモリは大幅に増えていることから、空間計算量を気にするよりは時間計算量を気にすることの方が効率的なアルゴリズムを求めることができます。

そのため、単に計算量というと時間計算量を指すことが多いでしょう。 （この記事でも以下「計算量」を「時間計算量」と指す）

オーダー記法を使おう

さて、ここまでの解説で計算量という指標を使用し、より効率的なアルゴリズムを測ることができるということはわかりましたが、具体的にはどうやって測るのでしょうか。

計算量は一般に、オーダー記法（$O$記法）と呼ばれるものを使用することで、どれぐらい計算量が必要になるのかというのを表すことができます。

ただし、プログラムの処理は実行マシンやメモリ容量、プログラミング言語などによって影響されるため、厳密な計算量は計れません。

ですので、オーダー記法というのは大雑把にこれぐらい早くなるよとか、こっちの処理の方が効率がいいよなどを評価するものと思ってください。

そして、オーダー記法は $O(1)$ や $O(N)$ 、$O(N^2)$ などの表記で表されます。

詳細はこの後説明しますが、「この処理は $O(N^2)$ になってるから、ここの処理を変えると $O(N)$ になって今より処理速度が早くなるよ」といった感じで、オーダー記法の種類には実行速度が早くなる順序があったりするので、よくある代表的なものだけでも覚えておくと良いと思います。

オーダー記法の考え方

オーダーは先述でもある通り$O(1)$ や $O(N)$ 、$O(N^2)$ などがありますが、ここで出てくる $N$ はデータ（要素）の個数を表している物です。

例えば $O(N)$ の場合は、データ $N$ に比例してプログラムの実行回数が表されます。

例として、100万件のcsvを繰り返して何かしらの処理を実行するとしたら、100万に比例した回数の処理が実行されるということになります。

// $csvは100万件なので100万回のループとなる
foreach ($csv as $cols) {
    echo $cols[0] // 何かしらの処理1
    echo $cols[1] // 何かしらの処理2
}

この場合はループの中で2回処理が実行されるので、100万件 × 何かしらの処理2回 = 200万 で 200万回の処理が実行されることになります。

$O(N^2)$ の場合は、2重のループなどが当てはまります。

// $csvは100万件なので100万回のループとなる
foreach ($csv as $cols) {
    // csvの項目は100項目なので100回のループとなる
    foreach ($cols as $cal) {
        echo $cal // 何かしらの処理1
    }
}

1行に100項目のデータがあるとしたら 100万件 × 100項目 × 何かしらの処理1回 = 1億 となるので、1億回の処理が実行されることになります。

ですので、大雑把に $O(N)$ より $O(N^2)$ の方が処理が大きくなるということがわかるでしょう。

小さい数値は無視する

大雑把に処理の評価はできますが、実際のプログラムでは $N$ や何かしらの処理がピッタリになることはほとんどないため、オーダー記法は以下の考え方で大雑把に評価します。

オーダー記法はデータ（要素）の数を数百件や数千件のものではなく、0または∞に近い数値で評価します。

最初の例の場合は何かしらの処理が2回あったので $2N$ と表しますが、誤差の範囲でしかないのでオーダー記法では係数を省略して $O(N)$ と表記されます。（$O(2N)$ ではないよ🙅‍♂️）

何かしらの処理が3つとなり $3N$ となったとしても同様に誤差として係数を省略するのです。

さらに、ある処理の中で複数のステップがある場合は $N^2+3N+1$ のように複数の表記がされると思いますが、ステップ数が一番大きい物以外を省いて考えます。

$N^2+3N+1$ の中では $N^2$ が一番ステップ数が多いので単に $N^2$ と表記されるということです。

以上のことからある処理を $N^2+3N+1$ と表せられたとしたら、最終的には $O(N^2)$ という表記となります。

このように「大体 $N^2$ に比例する実行回数が必要なアルゴリズムだな」というざっくりとした評価ができます。

代表的なオーダー記法の種類

ここでは概要だけ紹介します。

詳細の方は ほげさんの記事 や参考にした こちら の記事をみてください

$O(1)$

一番計算量が少ないもので、定数時間と呼びます。

データ量にかかわらず、定数の回数だけで処理回数が完了するものです。

配列のインデックスアクセスや、（線形）リストの先頭への要素追加や先頭要素の削除などが当てはまります。

$O(N)$

データの数に比例して処理時間がかかります。線形時間と呼びます。

配列などのループ

$O(N^2)$

線形時間より遅い2重ループなどが当てはまります。二乗時間と呼びます。

$O(N^2)$ を見つけたら見直しポイント

$O(log N)$

二分探索などで処理を減らすアルゴリズムで、対数時間と呼びます。

これ以上は改善する必要がないもので、ソート済み配列の二分探索などで使用されます。

計算量の大小

ここまで読んで、計算量の大小が分かったのではないでしょうか。

今回例であげた代表的なもので比較すると以下のような比較になります。

ここを意識して実装できるようになるとまた初心者から一歩成長できると思います！

おわりに

これで「計算量ってなに？」って状態からは脱却できたのではないでしょうか。

計算量を求めるには具体的に処理を見て判断したりするので、サンプルのコードを見ながらの方がわかりやすいのですが、この記事では導入ということで具体的な求め方は省きました。

最初にも言ったように、この記事を読んで「そもそも計算量とは？」って状態から脱却できたら、ほげさんの記事を読み返してみると面白いと思います！

そして、今後は「動く機能を作れる」から「パフォーマンスを考えた上で機能を作れる」って状態を目指していきたいなと思います。

さて、次回の記事はアドカレ初登場のミライト代表 hiroさん の記事です。
どんな記事が書かれるか楽しみですねー！

参考

• 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 – Qiita
• W – 2.06.計算量 – AtCoder
• 計算量オーダーについて – Qiita
• 計算量同士の比較と入力サイズによる比較 | アルゴリズムロジック