計算量 | Programming Place Plus　アルゴリズムとデータ構造編【導入】　第１章

トップページ – アルゴリズムとデータ構造編

この章の概要 🔗

この章の概要です。


計算量 🔗

アルゴリズムの性能を評価するために、計算量という指標を使うことがあります。

計算量には、時間計算量と空間計算量とがあります。前者は処理時間がどれだけ掛かるのかを表し、後者はどれだけの記憶容量を必要とするかを表します。多くの場合、単に計算量と言えば、前者の時間計算量のことを指します。

計算量は、単純に「５秒掛かる」のような表現を取るわけではありません。そもそも「５秒」というのは、ある特定のコンピュータでの結果に過ぎません。他のコンピュータで試すと、結果は大きく変動するかもしれませんから、性能評価の方法として適切とはいい難いのです。

そこで、「秒」のようなものを使わず、「命令数」のような方法を利用します。１つの命令を実行するための時間は環境によって異なっても、同じ言語で同じように実装されたアルゴリズムの命令数は変わらないので、これを基準とします。

Ｏ記法 🔗

実際に計算量を表現するに当たっては、よく、Ｏ記法（オーきほう）という表記法が使われます。この「Ｏ」はオーダーから来ています。

たとえば、O(n) のように記述し、この場合、データの個数 n に比例した時間がかかることを表します。よく登場するパターンは次のとおりです。

表記 意味 例
O(1) 定数 配列を添字アクセスする場合
O(log n) 対数 二分探索（【探索】第４章参照）
O(n) １次 線形探索（【探索】第１章参照）
O(n log n) n log n クイックソート（【整列】第８章参照）
O(n2) ２次 ２重ループを伴う配列全体の走査。バブルソート（【整列】第３章参照）など
O(n3) ３次 ３重ループを伴う配列全体の走査。行列計算など
O(2n) 指数 集合分割問題

計算量を用いることで、O(n) のアルゴリズムでは、データの個数n が 2倍になれば、処理時間も 2倍になるであろうという予測が立ちます。ここで n がいくつなのかも、処理時間が何秒なのかもまったく登場しないことがポイントです。特定の環境に依存せずに、アルゴリズムの性能が評価できるというわけです。

この表で上の方にあるほど、計算量が小さい、効率的なアルゴリズムです。しかし、現実的には必ずしも、効率的なアルゴリズムほど高速であるとはいえないことに注意が必要です。

まず、データの個数を表す n は、それなりの大きさがあることを前提としています。小さなデータ列を対象とすると、O(n) よりも O(n log n) の方が高速である可能性もあります。しかし、データ列が大きくなっていけば、歴然とした差が出てきます。

たとえば、n = 10 程度なら、O(n2) のアルゴリズムを使っても問題ないでしょう。しかし、n = 100000 になったら、相当にひどい結果になることが予想できます。

最悪と平均 🔗

同じアルゴリズムでも、どんな状況下での計算量を調べるかによって、性能が大きく違って評価されてしまいます。

たとえば、配列全体の中から特定の値を探す線形探索（【探索】第１章参照）のアルゴリズムを考えます。簡単にプログラムを書くと、次のようになります。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = { 5, -4, 7, -8, 13, 1, -6 };
    int target = 7;

    for( size_t i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        if( array[i] == target ){
            puts( "見つかりました。" );
        }
    }

    return 0;
}

実行結果：

見つかりました。

この場合、配列の要素数は 7 なので、データ数 n は 7 です。

もっとも多くの処理を重ねるパターンは、配列全体を探した結果、結局見つからなかった場合です。この場合、for文の中身が 7回実行されることが分かります。

逆に、一番少ない処理で済むパターンは、array[0] == target が成立する場合です。この場合、for文の中身を 1回実行するだけで済みます。

したがって、最悪時は n回、最良時は 1回となり、平均的に言えば n/2回だということです。これをそれぞれＯ記法で表記すると、O(n)、O(1)、O(n) です。

３つ目が O(n/2) とならないのは、Ｏ記法では定数の部分を無視するルールがあるからです。

なぜ無視できるかというと、計算量とは「データ数 n が増加していったとき、計算量がどのように変化していくか」を示すものであるためです。線形探索の平均比較回数は n/2回ではありますが、n が 10 のときは 5回、100 のときは 50回、1000 のときは 500回というような、n との関係性だけをみるので、これは O(n) に他ならないということです。

最悪時、最良時、平均時のように、見方によって結果が変わってしまうのでは、どれを採用するかによって、性能評価が大きく変わってきてしまいます。

多くの場合、最悪時の計算量を使います。理論的に非常に高速に動作する可能性があるとしても、最悪な場合があり得る限り、悪い方を基準とした方が無難だと言えます。すると、線形探索の計算量は O(n) と表現されます。

一方、最悪なパターンというものがまず起こらないようなアルゴリズムでは、平均的な計算量を使うこともあります。ですから、複数のアルゴリズムの性能を比較するときには、それぞれ、最悪時の計算量なのか、平均時の計算量なのかを確認しなければなりません。

実際の処理時間 🔗

計算量によって、アルゴリズムの性能評価ができ、これを元にいくつかのアルゴリズムの性能比較ができます。

しかし、実際に興味があるのは、結局のところコンピュータ上でどれだけの処理時間がかかるのかです。理論上、あるアルゴリズムが効率的であると分かっていても、実測した結果、それでも遅いとなれば何とか対策を講じなければなりません。

現実的な路線で考える場合、計算量だけでは、１回分の実際の処理時間が考慮されていないことが問題です。ここでの「１回」というのは、先ほどの線形探索のプログラムで言えば、for文を１回繰り返すことに相当します。ですから、他のアルゴリズムに取り替えたとき、そのアルゴリズムの for文の中身が線形探索のときよりもずっと複雑になるとすれば、計算量としては O(n) から O(log n) に改善されたとしても、現実の処理時間は増加する可能性があるのです。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

　平均計算量に関する記述を修正し、その周囲を少し加筆。

　新規作成。


前の章へ　（第０章　はじめに）

次の章へ　（第２章　パフォーマンスの測定）

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る