【アルゴリズム】Big Oの定数切り捨てルール・償却計算量を解説

こんにちは。タクマ™ [@suwaru_blog] です。

前回 Big O 記法の概要について解説しました。

Big O 記法は計算量の「割合」をざっくり表現するものです。
なので話をシンプルにするためのルールが存在します。

Big O [オーダー] 記法のルール

定数は切り捨てる

Big O 記法はあくまで計算量増加の「割合」、実行時間の「規模の程度」を表わすものです。
実際の数値がどうか？…までは考慮しません。

しかも「実行時間の定数は切り捨てられる」のが通常です。

特定の入力に対して O(1) より O(N) の方が早くなることも、
特定の入力に対して O(N) より O(N^2) の方が早くなることも現実にありえます。
そんな中、定数をいちいち議論しているのは不毛という考え方がされるのです。

並列のループ処理の数だけで判断できない

次のどちらのコードが高速か？その結論は「考えるだけムダ」です。

O(n)

ループが 1 つなのでオーダーは O(n) です。

/*
 * O(n)
 */

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

// min と max
for (int x: array) {
    if (x < min) min = x;
    if (x > max) max = x;
}

O(2n)

ループが 2 つなのでオーダーは O(2n) です。

/*
 * O(2n)
 */

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

// min だけ
for (int x: array) {
    if (x < min) min = x;
}

// max だけ
for (int x: array) {
    if (x > max) max = x;
}

O(N) の方が O(2N) より早いと思うかもしれませんが、一概にそう言えません。

それは非常に複雑な計算になるのでループ処理の数だけで判断できません。
なので Big O 記法は O(2N) も O(N) として扱うのです。

あまり細かいことは気にするな、ということです。

影響の少ない項も切り捨てる

また Big O 記法では、定数の他に「和の式」も切り捨てる傾向にあります。

実行時間において「和の式」で表す場合

ただし O(B^2 + A) のように、
種類の違うものが和の式でくっついているときは切り捨てることができません。

複数パートから成るアルゴリズムの計算時間

for 文が 2 つ連続する場合、
O(A + B) になるのか O(A * B) になるのか理解する必要があります。

実行時間を足すパターン O(A + B)

次の 2 つの for 文の合計の計算量は O(A + B) になります。

/*
 * A の処理から行い、それが終わったら B の処理を行う
 */

for (int a: arrA) {
    print(a);
}

for (int b: arrB) {
    print(b);
}

実行時間を掛けるパターン O(A * B)

次の 2 つの for 文の合計の計算量は O(A * B) になります。

/*
 * A の処理を行うたびに B の処理を行う: 多重ループ構成
 */

for (int a: arrA) {
    for (int b: arrB) {
        print(a + "," + b);
    }
}

償却計算量とは

最悪ケース・最善ケースでオーダーが異なる場合、
両方のオーダーを考慮する必要があるように思えます。

しかし、最悪ケースが起きたあとに次回の最悪ケースまでに時間がかかる場合、
その計算コストは償却されることがあります。

重い処理はたまにしか発生しないので無視しよう！という考え方ですね。
そのような計算量を「償却計算量」といいます。

要素を挿入する場合の実行時間

配列リスト・動的な可変長配列などはそのサイズに柔軟性が与えられています。
多くのプログラミング言語では、要素いっぱいの配列に挿入しても問題ない仕様になっています。

以上を踏まえて、動的配列への要素挿入コストを考えてみましょう。

最悪ケース・最善ケース

空っぽの配列に対して、N 個の要素を順番に 1 つずつ挿入していく場合、
計算量オーダーは以下のようになります。

最悪ケースはあまり起こらないので償却するとしましょう。
そうなると償却計算量は最善ケースの O(1) だけかかることになります。

最悪ケースを求める

サイズ N の配列があるとき、
容量が増えるたびに何個の要素をコピーする必要があるか？という視点で考えてみましょう。

N 個の要素を追加する際のコピー回数は N/2 + N/4 + N/8 + N/16 + ... + 2 + 1 となります。
この合計は N を超えないので、要素の追加の最悪ケースは O(N) となるわけです。

1 つ挿入するごとの計算量 (償却計算量) は基本的に O(1) だけど、
N 個の要素挿入において、最悪ケースで O(N) の計算量が発生しうる…ということです。

しかし最悪ケースは頻発しないので、ならしで平均 O(1) とします。

CS シリーズ

次回

前回