ビッグ・オー記法(Big O)

O記法について学んだのでメモ

アルゴリズムとは

コンピュータを使って、ある目的を達成したり問題を解決するための処理手順のこと。
また、アルゴリズムに与える入力の大きさをNとした時、Nを問題の大きさという。

アルゴリズムの必須条件

アルゴリズムは次のような条件を満たしていなければならない。

1. 正しさ: 得られた処理結果は常に正しい。
2. 有限時間: 有限時間内に処理が終了する。

アルゴリズムの選択条件

一般的にアルゴリズムを選択する際には次のようないくつかの基準を考える。

• 時間計算量: これは単純に環境によって変わりうる「処理時間」を評価たものではなく、各処理の実行回数である「ステップ数」を評価したものである。時間計算量は小さい程良い。
• 空間計算量: これはメモリ使用量の指標のことであり、こちらも小さい方が良い。
• わかりやすさ・実現しやすさ: 上二つに優先するものではないがアルゴリズムはわかりやすく、また実装しやすい方が良い。
• 問題の大きさ: 時間計算量も空間計算量も実際には問題の大きさに依存する。通常はnが十分に大きい場合を評価するが、対象の問題の大きさ範囲内でアルゴリズムを選ぶべきである。

どの基準を優先すべきかは状況にもよる。
基本的には上記であげたような項目を総合的に加味して最良のアルゴリズムを選択する必要がある。

なお、計算量は一般的に次のビッグ・オー記法によって表される。

ビッグ・オー記法

一般的に、アルゴリズムの計算量は、問題の大きさNが十分に大きい場合を想定して評価する。
問題の大きさを表すパラメータNを用いて(時間・空間)計算量を記述し、nが大きくなるにつれて計算量がどの程度増加するのかについて考える。つまり、計算量がパラメータNに関してどのような関数形で表現されるかに着目する。
このような計算量の表現方法をビッグ・オー記法(O記法)という。

O記法では、計算量をNの関数として記述し、Nに関する主要項のみを残して、他の項は無視する。
主要項とは、Nの増加に伴ってもっとも早く増加する項である。
また、主要項の係数も無視すると、最終的に1, logN, N, NlogN, N^a, a^N のような形となる。これらをアルゴリズムのオーダといい、O(1), O(logN), O(N) のように記述する。

ここで上記の代表的なオーダを小さい順にまとめておく。

1. O(1): 理想。問題の大きさnに依存しない定数値。これより小さいものは存在しない。
2. O(logN): これは非常に小さい。
3. O(N): これも小さい
4. O(NlogN): 小さいと言ってもよい。logN は非常にゆっくりなので、O(NlogN)はO(N)とあまり大差ない。
5. O(N^2): これは許されないほどではないがかなり大きい。これ以下のものにすべき。
6. O(N^3): 限界。これより大きいものは許されない。
7. O(a^N): これは指数オーダーと呼ばれ、アルゴリズムとは呼べないほど遅い。

具体的な計算は例えば以下のようになる。

• O(2N) -> O(N)
• O(N^2 + N) -> O(N^2)
• O(N + logN) -> O(N)
• O(5*2^N + 1000*N^1000) -> O(2^N)

次に、ビッグ・オー記法も交え、時間計算量、空間計算量について具体的に見ていく。

計算量

アルゴリズムを実行時間で評価する際の目安となるが時間計算量であり、通常はステップ数を用いて表現する。
また、メモリ使用量に基づいてアルゴリズムを評価する空間計算量がある。
以下、初項a、項比rの等比数列の初項から第n項までの和を求めるアルゴリズムを例にこれらの計算量について考えてみる。

なお、和を求める方法として真っ先に思いつく方法は、等比数列の和の公式で求める方法と等比数列の一般項の公式で初項から第n項まで足し合わせる方法だろう。
他には初項から第n項までの値が既知であるとして単純に和を取る方法もある。

ここでは以下の３つの式を扱う。

1. Sn = a * (r^n - 1) / (r - 1)
2. Sn = a + a * r + a * r^2 + ... + a * r^(n - 1)
3. Sn = a1 + a2 + ... + an

式1~3の各ステップを書き下すのは大変なので、ここではアルゴリズムをプログラムの形式で表してみる。

式1は以下のようになるだろう:

s1: let mut s = r;
s2: for _ in 0..(n - 1) {
s3:   s *= r;
s2: }
s4: s -= 1;
s5: let x = r - 1;
s6: s /= x;
s7: s *= a;
s8: println!("{}", s);

式2は以下のようになる:

s1: let mut s = 0;
s2: for i in 1..=n {
s3:   let mut x = a;
s4:   for j in 0..(i - 1) {
s5:     x *= r;
s4:   }
s6:   s += x;
s2: }
s7: println!("{}", s);

式3は以下のようになる:

s1: let mut s = 0;
s2: for e in a.into_iter() {
s3:   s += e;
s2: }
s4: println!("{}", s);

上記をもとにまず時間計算量を考えてみる。

時間計算量

時間計算量はステップ数をO記法で評価するのだった。
上記で紹介した式1 ~ 式3 の各アルゴリズムのステップ数をまとめてみると以下のようになる。

上記より、それぞれのオーダーは、O(n)、O(n^2)、O(n) になったので、上記３つのアルゴリズムの中では、式1と式3が時間計算量の面で優れていると評価できる。
まったく同様の結果を得るアルゴリズムでもステップ数にこれだけの差が現れることから、アルゴリズムの重要性がわかるというものだ。

なお、式2の内側のループはi-1回行われるものであり、それが外側のループにより計n回行われているので、合計ステップ数は n(n - 1)/2 になる。
この計算には等差数列の和の公式が使える。

等差数列の和の公式: n(a + l)/2 : 1 + 2 + 3 + .. + n = n(n + 1)/2
∑(i=1, n) i = n(n + 1)/2
∑(i=1, n) i - 1 = n(n - 1)/2

他に簡略化のために、時間計算量についてはいくつか覚えておいた方が良い考え方がある。

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

複数パートからなるアルゴリズムの時間計算量を求めるときには、和として計算すべきか積として計算すべきかについて常に把握していなければならない。
これは、時間計算量を評価する際の簡略化にもつながるので頭の中に入れておきたい。

• アルゴリズムが「処理Aを行い、それが終わったら処理Bを行う」場合は実行時間の和O(A + B)を考える。
• アルゴリズムが「処理Aを行うたびに処理Bを行う」場合には実行時間の積O(A * B)を考える。

例: 実行時間を足す: O(A + B) :

for e in a.iter() {
  println!("{:?}", e);
}
for e in b.iter() {
  println!("{:?}", e);
}

例: 実行時間を掛ける: O(A * B) :

for ea in a.iter() {
  for eb in b.iter() {
    println!("{:?}, {:?}", ea, eb);
  }
}

以上を踏まえれば、式1 ~ 式3 の時間計算量の評価も簡略化できる。
たとえば、単純に、f(n)の主要項になりうる部分はループ処理であるから、ここに着目して、式1、式3の時間計算量はO(n)に、式2の時間計算量は、問題の大きさnに関係する２重ループに注目すると、内側のループ回数は平均してn/2回ぐらいであり、外側のループはn回であるから、全体としてn^2/2回ぐらいになり、時間計算量がO(n^2)であると判断することができるだろう。

内側のループ回数は 0, 1, 2, ... N と増えていき、
総和が 0 + 1 + 2 + ... + Nだから、平均値はその中央値のおよそN/2回と言える。
BigOでは細かい部分は気にしなくてもいい。

対数オーダー(LogN)の時間計算量

時間計算量がO(logN)になる代表的なデータ構造・アルゴリズムといえば、二分探索。平衡二分木が例に挙げられる。
逆に、探索空間の要素数が毎回半分になっていくようなアルゴリズムやデータ構造の場合には、その時間計算量はO(logN)になると予想してよい。

二分探索を例に考えてみる。
要素数がNの配列からスタートし、一回のステップで探索を行う要素数が N/2 になる。次は N/4 になり、N/8 になり、最終的に要素数が1になったところで探索を終了する。
時間計算量は、Nを繰り返し2で割った時、N から 1 になるまで合計で何ステップあるかということになるが、
逆に言えば、1 から N になるまで合計何回２をかければ良いかという問題に帰結できる。

したがって、求めたいステップ数を k とすると:

2^k = N
<=> log2 2^k = log2 N
<=> k = log2 N
= O(log N)

となり、上記の通りステップ数(時間計算量)は O(log N)になる。
なお、BigO においては、対数の基数が異なっても、基数を揃えたときには高々定数倍の係数にしかならないため無視されることを覚えておきたい。

再帰の時間計算量:
再帰の実行時間は、再帰の中での呼びだしの数に依存するので注意が必要。
たとえば、複数の呼び出しを行う再帰関数の場合には、実行時間は、再帰関数内での呼び出し数を枝の数として、O(枝の数^深さ)になる場合が多い。

例:

fn (n: usize) -> usize {
  if n <= 1 {
    1
  } else {
    f(n - 1) + f(n - 1)
  }
}

例えば、上記はn=4の場合、f(4)から、f(3) x 2 となり、そこから、f(2) x 4 となり、f(1) x 8 となるので、深くなるたびに、一つ上の呼び出しの二倍呼び出されることになる。よってこのアルゴリズムの時間計算量はO(2^N)であると言える。

関数はリターンすればスタックは戻るので、一度に生じるノードは最大でO(N)で空間計算量はO(N)である。

最悪、期待、償却実行時間

等比数列の和を求めるアルゴリズムのように、問題の大きさnが決まると時間計算量が一意に定まるアルゴリズムがあるが、一方で、データや実行のタイミングなどによって時間計算量が変動する場合もある。

そのようなアルゴリズムでは乱択化を利用している場合がある。乱択化では、格納されているデータや実行する操作に加えて、サイコロの出目も踏まえて実際の処理を決める。乱択化を利用する場合には実行時間は形式的には確率変数であるので、そのようなデータ構造・アルゴリズムを分析するときには期待値(期待実行時間)を考えるのが良い。

これとは別に償却実行時間という考え方もある。操作列の中でたまに通常の操作とはコストの異なる最悪なケースがおきる場合がある。ただし、一度最悪ケースが起きたあとに次回の最悪ケースまでに時間がかかる場合、その計算コストは償却されると言う考えだ。

いずれの場合も、もちろん最悪なケースも指標として考えることができる。これを最悪実行時間という(コインを５回投げるとする。表がでたら処理を終了するとして５回とも裏が出るケースなど)。

• 最悪実行時間: 実行時間に対する保証の中で最も強力。最悪実行時間がf(n)としたら、ある操作の実行時間がf(n)を超えることは決してない。
• 期待実行時間: 期待実行時間がf(n)であるとは、実行時間が確率変数であり、その確率変数の期待値がf(n)であることを意味する。操作のランダム性による。
• 償却実行時間: 償却実行時間がf(n)であるとは、典型的な操作にかかるコストがf(n)を超えないことを意味する。
正確には m 個の操作にかかる実行時間を合計してもm*f(n)を超えないことを意味する。いくつかの操作にはf(n)より長い時間がかかるかもしれないが、操作の列全体で見れば、１つあたりの実行時間はf(n)という意味。

期待実行時間と最悪実行時間の例

次の問題を考えてみる:

重さのこのとなるコインが五個あり、この中に 30g のコインが含まれている確率は 1/2 である。はかりを使って 30g のコインがあるかどうかを調べて、ある場合は「あり」をない場合は「なし」を出力する。

アルゴリズムを考えると以下のようになるだろう。

1. まだ量っていないコインがあれば、一つをはかりにのせる。
すべて量っていたら3.に進む。
2. はかりが 30g を示していたら「あり」を出力して、終了する。
そうでなければ、1.に戻る。
3. 「なし」を出力して終了する。

この例では、コインの重さを図る回数が時間計算量になるが、コインの重さを図る回数は、どのコインの重さが 30g かで変動する。
最低で一回、最悪の場合は五回の動作が必要だ。このような場合に最悪実行時間と時間計算量の期待値を表す期待(平均)実行時間を考えることができる。

上記で述べたアルゴリズムでは、コインの重さを図る回数は、１〜５回のいずれかとなり、確率はそれぞれ 1/10, 1/10, 1/10, 1/10, (1/10 + 1/2) となるので、期待実行時間は、

1*1/10 + 2*1/10 + 3*1/10 + 4*1/10 + 5*(1/10 + 1/2) = 4

となる。したがって、最悪実行時間は5で、期待実行時間は4である。

償却実行時間と最悪実行時間の例

たとえば、Rustのベクタは要素を追加削除していくことができるが、予め確保しているメモリが足りなくなったときにはメモリの再割当てを行う。
これは、より広い領域を確保して、要素をコピーすることになる。
ここでは、簡単化のためにバッファに配列を使用していると考えてみる。また、この配列が足りなくなったとき、その２倍の新しい配列を確保し、そこへすべての要素をコピーするものとする。

そうすると、配列がいっぱいになったとき要素数がNであれば、新しく領域確保した配列への要素のコピーにO(N)の時間を要する。
サイズ2Nの新しい配列にN個の要素をコピーするからである。

しかし、この内部操作は毎回起きるわけではない。ほとんどの場合 push にかかる実行時間はO(1)である。
したがって、resize()のようにコストも大きい操作もあるが、全体の操作列で均せば１つの操作あたりの償却コストはO(1)とみなせる。
これを償却実行時間といい、このように拡大と縮小のコストを加味しても平均的な実行時間にはほぼ影響しない場合に、最悪実行時間とともに考えることができる。

最悪の場合はたとえば、リサイズによるコピーが発生する場合で配列にN個の要素があればO(N)になる。

また、最初から最後まで続けてX個の要素を追加のみした場合を考えてみる。
配列のサイズを２倍にするたびにコピーが発生するので、逆算するとX + X/2 + X/4 + X/8 + ・・・ + 1 で (2X) つまり、トータルでO(X)の時間を要すると言える。ただし、それでもやはり均してみれば、挿入ごとの償却実行時間はO(1)であると言える。

空間計算量

次にアルゴリズムの空間計算量（メモリ使用量）について考える。
メモリには入力データや計算結果を表す値が保持されるので、単純にはアルゴリズムの実行に必要な値の個数がメモリ使用量の目安になる。
他には再帰呼び出しにより積まれたスタック領域の消費量も考える必要がある。

等比数列の和を求める式1~式3では、再帰はなく、入力データ用と計算用に下記表に示した個数の値を使用する。

上記踏まえると式3の空間計算量はO(n)となり、空間計算量の観点からはあまり良いアルゴリズムとは言えない。

スタックを消費する例についても考えておかなければならない。
以下のようなプログラムがあるとする。下記のコードはO(n)の実行時間とO(n)の空間使用量になる。

fn sum(n: i32) -> i32 {
  if n <= 0 {
    0
  } else {
    n + sum(n - 1)
  }
}

関数呼び出しは、呼び出しごとにスタックに積まれ、その分実際のメモリを消費する。

sum(4)
  => sum(3)
    => sum(2)
      => sum(1)
        => sum(0)

もちろんn回呼び出すからと言って関数呼び出しの空間計算量がO(n)になるわけではない。
再帰呼び出しでなくて、スタックに積んだままにならないのであれば、スタック上に同時に存在するわけでないので関数呼び出しにはO(1)のメモリ使用量が必要なだけになる。