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

  • このエントリーをはてなブックマークに追加
  • Pocket

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

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

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

今回は Big O の基本的なルール・注意点・償却計算量について解説します!

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

定数は切り捨てる

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

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

O(2N) であっても O(N) と表現される、ということです。

特定の入力に対して 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(N^2 + N)
    • + N の部分は定数ではない…がさほど重要ではない
    • + N の部分を切り捨てて O(N^2) と考える
  • O(2N^2)
    • O(N^2 + N^2) と言い換えることができる
      • + N^2 の部分を切り捨てて O(N^2) と考える
    • ※ 結果的に 2N^2 の 2 という定数を切り捨てて O(N^2) にするのと同じになる
  • O(N + logN)
    • + logN の部分を切り捨てて O(N) と考える
  • O(5*2^N + 1000N^100)
    • 5*1000N^100 の部分を切り捨てて O(2^N) と考える

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

ただし 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);
    }
}

償却計算量とは

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

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

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

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

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

要素挿入によって配列がいっぱいになった場合、配列クラスが「その容量 2 倍の配列を作って、中身コピーして、配列そのものを置き換える」…ということを裏側でしています。

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

最悪ケース・最善ケース

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

  • 配列がいっぱいじゃないとき
    • 空いてるスペースに要素を挿入するだけ
    • オーダーは O(1) になる
    • 「配列がいっぱいじゃないとき」は最善ケース
  • 配列がいっぱいのとき
    • サイズ 2 倍の新しい配列をつくって N 個の要素すべてをコピーする
    • オーダーは O(N) になる
    • 「配列がいっぱいのとき」は特定のタイミングで起こる最悪ケース

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

最悪ケースを求める

  • 空っぽの配列からはじまって、配列が一杯になるたび配列サイズが 2 倍になる
    • 配列サイズが 2 のべき乗のとき、配列サイズを 2 倍にする必要がある
  • 配列サイズが 2^0, 2^1, 2^2, 2^3, 2^4 … N のときが最悪ケース: O(N)

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

  • 最初の容量増加: 2^0
    • 1 個の要素をコピーする
  • 2 回目の容量増加: 2^1
    • 2 個の要素をコピーする
  • (中略)
  • その前の容量増加
    • N/16 個の要素をコピーする
  • その前の容量増加
    • N/8 個の要素をコピーする
  • その前の容量増加
    • N/4 個の要素をコピーする
  • 最終的な容量増加
    • N/2 個の要素をコピーする

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

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

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

CS シリーズ

次回

前回

お仕事ください!

僕が代表を務める 株式会社 EeeeG では Web 制作・システム開発・マーケティング相談を行っています。
なにかお困りごとがあれば、Twitter DM や Web サイトからお気軽にご相談ください。

コメント

コメントを残す

*