アルゴリズムとデータ構造編【導入】 第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) に改善されたとしても、現実の処理時間は増加する可能性があるのです。


参考リンク

プログラミング作法
 -- 「2.5 O記法」の表を一部引用。。

更新履歴

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

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

'2011/10/22 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ