C++で学ぶカウンター増分操作の償却分析：計算量を正しく理解する

償却分析（Amortized Analysis）とは、一連の操作に対して必要となる平均的な実行時間を求めるための解析手法です。これはアルゴリズムの平均ケース解析とは異なります。償却分析は常に平均ケースを想定するわけではなく、最悪ケースが発生する状況も考慮に入れます。そのため、償却分析は「一連の複数操作に対する最悪ケース解析」と捉えることができます。

一連の操作では、それぞれの操作にかかるコストが異なり、中には非常に高いコストがかかるものもあります。本記事では、この概念を理解するために、2進カウンター（バイナリカウンター）を例に挙げて解説します。

それでは、C++での動作と実装を見ながら、概念をしっかりと身につけていきましょう。

kビット2進カウンターの仕組み

kビットの2進カウンターは、長さkの配列で表現され、初期値はすべて0です。この値に対して、インクリメント（1加算）操作を繰り返し実行します。8ビットの2進配列がインクリメント操作によってどのように変化するかを見てみましょう。

00000000 → 00000001 → 00000010 → 00000011 → 00000100 → 00000101 → … → 11111111

このロジックは、数値の最下位ビットから見て最初に現れる0を探し、そのビットを1に反転させるとともに、それより下位の連続する1のビットをすべて0に戻すというものです。

C++での実装例

#include <iostream>
using namespace std;

int main() {
    int number[] = {1, 0, 0, 1, 0, 1, 1, 1};
    int length = 8;
    int i = length - 1;

    // 最下位ビットから連続する1を0に反転
    while (number[i] == 1) {
        number[i] = 0;
        i--;
    }

    // 最初に見つかった0を1に反転
    if (i >= 0)
        number[i] = 1;

    for (int i = 0; i < length; i++)
        cout << number[i] << " ";
}

出力結果

1 0 0 1 0 0 0 0

入力 10010111 にインクリメント操作を行うと、最下位ビット側から連続する3つの「1」が「0」に反転され、その直前の「0」が「1」になるため、結果は 10010000 となります。

償却分析による計算量の評価

この問題において、各操作のコストは一定ではなく、反転が必要なビット数に依存します。しかし、n回の一連の操作全体として見た場合の漸近的な計算量は O(n) となります。

n回の操作で行われるビット反転の総回数は次のように表せます。

n + n/2 + n/4 + … + n/k²

ここで、kは反転回数に関わる項です。この級数は分母が等比数列（公比1/2）になっているため、合計は有限の値に収束します。

Sum = n + n/2 + n/4 + … + n/k² < n / (1 − 1/2) = 2n

したがって、1回あたりの償却コストは以下のように計算できます。

償却コスト = O(n) / 2n = O(1)

まとめ

この結果から、1回のインクリメント操作の償却コストは O(1)、つまり定数時間であることが分かります。個々の操作には最大でk回のビット反転が発生する可能性がありますが、長期的に見れば平均コストはビット数nに比例しないことが、償却分析によって厳密に示せるのです。

このように償却分析は、一見すると高コストに見える操作でも、一連の操作全体で評価すれば効率的であることを証明するための強力な手法です。動的配列の拡張やハッシュテーブルの再構築など、実際のアルゴリズム設計にも広く応用されています。