アルゴリズムとデータ構造編【導入】 第1章 計算量

先頭へ戻る

この章の概要

この章の概要です。


計算量

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

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

計算量は、単純に「5秒掛かる」のような表現を取る訳ではありません。そもそも「5秒」というのは、ある特定のマシン上での結果に過ぎず、他の環境で試せば大きく変動してしまいますから、性能評価の方法として適切とはいい難いのです。

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

O記法

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

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

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

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

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

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

例えば、n = 10 程度なら、O(n2) のアルゴリズムを使っても何ら問題ないですが、n = 100000 になったら、相当にひどい結果を生むでしょう。

最悪と平均

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

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

#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;
    int i;

    for( 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記法で表記すると、O(n)、O(1)、O(n) です。

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

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

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

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

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

実際の処理時間

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

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

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


参考リンク



更新履歴

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

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

'2011/10/22 新規作成。



前の章へ (第0章 はじめに)

次の章へ (第2章 パフォーマンスの測定)

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

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー