O記法

大学でいい加減にしか学ばなかったO記法ですが、「『アルゴリズムC』が素晴らしい」と友達が言っていたので、勉強し直してみました。

アルゴリズムC・新版―基礎・データ構造・整列・探索

定義

関数 g(N) が O(f(N)) であるとは、定数 c0 と N0 が存在して、N > N0 であるすべての N に対して　g(N) < c0 f(N) が成り立つことである。

なるほど。(分らない人は、O(f(N)) をたとえば O(log N)と読み替えてみましょう。)

なお、g(N) ∈ O(f(N)) と書くのが適切ですが、g(N) = O(f(N)) と書くのが習慣として定着しています。後述するように O記法は、あたかも等式のように変形できる性質があるので、等号で結ぶ方が直感的だからです。

使用目的

• 数式において小さい項を無視した時に生ずる誤差の限界を示す
• プログラム全体の解析には影響の少ない部分を無視した時に生ずる誤差の限界を示す
• 総実行時間の上界によってアルゴリズムを分類する

最後の目的しか、意識していませんでした。^^;

基本規則

O記法が含む数式に対して、以下ように変形できます。証明は後述。

• f(N) → O(f(N))
• c O(f(N)) → O(f(N))
• O(cf(N)) → O(f(N))
• f(N) - g(N) = O(h(N)) → f(N) = g(N) + O(h(N))
• O(f(N)) O(g(N)) → O(f(N)g(N))
• g(N) = O(f(N)) のとき、O(f(N)) + O(g(N)) → O(f(N))

例

  (N + O(1))(N + O(log N) + O(1))
= N^2 + O(N) + O(N log N) + O(log N) + O(N) + O(1)
= N^2 + O(N log N)

つまり、N が大きいとき、この式の近似は N^2 であり、誤差の限界は O(N log N) です。

証明

以下に順に基本規則を証明します。

大前提として、N ≧ 0, f(N) > 0 です。c も正数です。

f(N) → O(f(N))

1 より大きな c に対して、どんな N でも f(N) < c f(N) となるので、f(N) = O(f(N))。

c O(f(N)) → O(f(N))

c O(f(N)) とは、g(N) / c < c0 f(N) となる c0 と N0 が存在することを意味する。

このとき、g(N) < c c0 f(N) である。N0 と c c0 が存在するので、右辺は O(f(N)) と表せる。

すなわち、c O(f(N)) = O(f(N))。

O(cf(N)) → O(f(N))

O(cf(N)) とは、g(N) < c0 c f(N) となる c0 と N0 が存在することを意味する。上記と同様に、O(cf(N)) = O(f(N))。

f(N) - g(N) = O(h(N)) → f(N) = g(N) + O(h(N))

証明1：アルゴリズムイントロダクションによれば、f(N) = g(N) + O(h(N)) とは、f(N) = g(N) + k(N) であるような関数 k(N) ∈ O(h(N)) が存在するという意味である。(a)

一方、f(N) - g(N) = O(h(N)) とは、f(N) - g(N) = k(N) としたときに k(N) ∈ O(h(N)) という意味である。(b)

(a) と (b) の意味はまったく同じである。

アルゴリズムイントロダクション 第1巻 数学的基礎とデータ構造

証明2：

f(N)=g(N)+O(h(N))が成り立たつという定理の主張は、∃N1,∃C,∀N>N1,k(N)N1,f(N)>=g(N)+Ck(N)。これが成り立つと仮定する。

f(N)-g(N)=O(h(N)) が成り立つので、∃N2,∃D,∀N>N2,f(N)-g(N)f(N)-Dk(N)。

N > max(N1,N2)を満たすNについて、f(N)>=g(N)+Ck(N)>f(N)-Dk(N)+Ck(N)となる。ここで、f(N) > 0, k(N) > 0 であり、E = C - D > 0 となる D と C を選んだ場合、f(N) > f(N) + E k(N) となり矛盾する。

よって、仮定が間違っており、f(N)=g(N)+O(h(N))が成り立つ。

O(f(N)) O(g(N)) → O(f(N)g(N))

F(N) < c0 f(N) となる c0 と N0 が存在し、また、G(N) < c1 g(N) となる c1 と N1 が存在するとき、2つの式を掛け合わせると、F(N)G(N) < c0 c1 f(N) g(N) となる。これは不等号を満たす max(N0, N1) と c0 c1 が存在することを意味しているから、O(f(N)g(N)) と書ける。

g(N) = O(f(N)) のとき、O(f(N)) + O(g(N)) → O(f(N))

条件により、g(N) < c0 f(N) を満たす N0 と c0 が存在する。

F(N) < c1 f(N) となる c1 と N1 が存在し、また G(N) < c2 g(N) となる c2 と N2 が存在するとき、両辺を足し合わせると、F(N) + G(N) < c1 f(N) + c2 g(N)。

条件より、F(N) + G(N) < c1 f(N) + c0 c2 f(N) < (c1 + c0 c2) f(N)。max(N0, N1, N2) に対して、c1 + c0 c2 が存在するので、O(f(N)) と書ける。

最後に

証明はイマイチな感じなので、随時変更して行きます。(_ _)