量理論とは,一見してつかみどころのないアルゴリズムを定量的に把握し,その良し悪しを評価する考え方である。

 アルゴリズム(Algorithm)とは,与えられた問題を解く手順のことだ。コンピュータの世界では,「プログラムによって問題を解く手順」ということになる。

 JIS(日本工業規格)は,アルゴリズムを次のように厳格に定義している。「明確に定義された有限個の規則の集まりであって,有限回適用することにより問題を解くもの。例えば,sin(X)を決められた精度で求める算術的な手順を,もれなく記述した文」(JIS X 0001-1987より)。

 注目して欲しいのは,「有限個の規則」と「有限回適用」という言葉である。アルゴリズムを構成する規則の個数と,それを適用した時の処理の回数が有限であることが,アルゴリズムの条件になる。

 したがって,それらの“数”からアルゴリズムの良し悪しを評価できることになる。例えば同じ問題を解くアルゴリズムが複数あったとしよう。この時,規則の個数あるいは適用回数の少ない方が,より優れたアルゴリズムというわけだ。

 なぜ規則の個数や適用回数が少ないと,優れたアルゴリズムなのか。それは,そうしたアルゴリズムは,結果的にメモリーの消費量が少なくなるか,問題を解くまでの時間が短くなるからである。

 このプログラムの実行に要するメモリー容量と時間は,アルゴリズムを定量的に評価する尺度としてよく用いられる。前者を「領域計算量」,後者を「時間計算量」と呼ぶ。両者を合わせて「計算量」と総称するが,通常は,メモリー消費量よりも実行時間を重視することが多いので,計算量と言えば時間計算量を指すのが一般的だ。

計算量はマシン性能と切り離す

 以下では具体的なアルゴリズムを例にとって,その良し悪しを評価してみよう。今回は「線形探索」と「2分探索」という,配列の中から目的のデータを見つける2つの代表的なアルゴリズムを取り上げる。要素数n個の配列A(1)~A(n)の中から,「33」というデータを見つけてみたい。

 線形探索は,配列の先頭から末尾まで,1つずつ順番に要素をチェックしていく単純なアルゴリズムである(図1)。最大n回のチェックによって,目的のデータを見つけることができる(または見つからないと判断できる)。仮に1回のチェックに要する時間をS秒とすれば,末尾の要素(n)で目的のデータが見つかった場合,線形探索プログラムの時間計算量は「S×n秒」となる。

図1●線形探索のアルゴリズム
図1●線形探索のアルゴリズム
検索対象のデータが見つかるまで先頭から順番に要素をチェックしていくアルゴリズム。要素はソートしなくてもよい

 一方,2分探索のアルゴリズムは,値の小さい順(大きい順でも構わない)に整列された配列を対象に,配列中央の要素をチェックする(図2)。配列中央の要素のデータが目的のデータなら,見つけたことになる。もしも「配列中央の要素のデータ>目的のデータ」なら,チェック対象を配列の前半に狭め,逆に「配列中央の要素のデータ<目的のデータ」なら,チェック対象を配列の後半に狭める。そして狭めた配列に対して再び中央の要素をチェックする。このようにして配列の2分割を繰り返してデータを見つけるので2分探索と呼ばれるのである。

図2●2分探索のアルゴリズム
図2●2分探索のアルゴリズム
あらかじめソートされた要素の中央に位置するデータと,検索対象のデータ(33)を比較し,その大小関係によって探索範囲を狭めていくアルゴリズム

 2分探索では,最後まで残った要素が目的のデータだった場合,チェック回数は「log2n」となる。なぜなら,要素数n個の配列を2分割することを繰り返して最後の1個になったのなら,同じ回数分だけ1個を2倍することを繰り返せば元のn個に戻るからだ。つまり,2をチェック回数だけべき乗すれば,n個となる。log2nは,「2をnにするための指数の値(nになるまで2を繰り返し掛けていく回数)」を意味している。

 時間計算量はどうなるだろうか。仮に1回のチェックと配列の2分割に要する時間をB秒とすると,時間計算量は,「B×log2n秒」となる。