アルゴリズムの計算量を見積もる「操作カウント法」とは

アルゴリズムの実行コストを見積もる方法はいくつかありますが、その一つが操作カウント(演算回数の計測)によるアプローチです。加算・減算・比較といった基本的な演算の中から一つを選び、その操作がアルゴリズム全体で何回実行されるかを数えることで、時間計算量を見積もることができます。

この手法を成功させる鍵は、時間計算量の大部分を占める操作を正しく見極める力にあります。どの操作をカウント対象に選ぶかによって、分析の精度や有用性が大きく変わるためです。

具体例：配列の最大要素のインデックスを求める

サイズ n の配列(添字は 0 から n-1)を考えます。このアルゴリズムは、配列内の最大要素のインデックスを返すものです。コストを見積もるには、配列の要素同士の比較操作が何回行われるかを数えます。

ここで重要なのは、カウント対象として選ぶのは一つの操作だけであるという点です。実際、このアルゴリズムにはループ変数 i のインクリメントや、インデックス変数への代入など、他にもさまざまな操作が含まれています。しかし、これらは今回の分析では考慮しません。

擬似コード

getMax(arr, n):
    index := 0
    max := arr[0]
    for i in range 1 to n - 1, do
        if arr[i] > max, then
            max := arr[i]
            index := i
        end if
    done
    return index

操作選択のポイント

コストを見積もる際には、最も多く実行される操作を選ぶことが大切です。例えばバブルソートを分析する場合、スワップ(要素の交換)操作をカウントするとしましょう。このとき、その操作がいつ最大回数になるのか(最悪ケースはいつ発生するのか)を意識しておく必要があります。

最悪の場合の実行回数を把握しておけば、分析時にアルゴリズムのコストの上限(最大値)を正確に評価でき、より信頼性の高い計算量の見積もりにつながります。