前回の復習

$\{w2w | w ∈ \{0, 1\}^*\}$ってどういう意味かと思ってたけど, $w$をスター演算の結果の一例として, $2$の両隣に同じ記号列があるということだったんですね.

big-O記法

時間計算量って高級言語だと, どの式や文がステップを消費してどの行為がステップを消費しないのか今ひとつわかりませんでしたが, チューリングマシンだと1ステップがハッキリしていて良いですね.

アルゴリズムの計算量は通常複雑な式になる. 漸近的解析と呼ばれる方法を用いて簡略化する. 最高次の項だけを考え, その項の係数やより低い次数の項を無視する.

$$f(n) = 7n^4 + 2n^2 + 10n + 5$$ なら $$f(n) = O(n^4)$$ にする.

$n = 1$の時, 前者は$24$, 後者は$1$になるが, $n = 10$の時, 前者は$70305$, 後者は$10000$で, $n$を増やしていくと差がなくなっていく.

$f$と$g$を2つの関数$f: N → R^+$とする. 全ての整数$n >= n_0$に対して正の整数$c$と$n_0$が存在して $$f(n) <= cg(n)$$ であるとき, $f(n) = O(g(n))$と書く.

直感的に言えば, $f(n) = O(g(n))$と書いた時定数倍を無視して$f$は$g$より小さいか等しいことを意味する.

$f(n) = O(\log n)$のように書かれるとき, 対数の底を気にする必要はない. 底が変わっても値は定数倍しか変わらないのでオーダー記法の場合は無視されるため.

small-O記法

big-Oとは違い, $$f(n) < cg(n)$$のように等しくなく小さいことを意味する.

アルゴリズムの解析

次のようなTuring機械$M_1$の時間計算量を調べる.

1. テープを全て走査し, 1の右側に0があれば拒否する
2. 0と1の両方がテープ状に残っているならば1つの0と1つの1をXで消すことを繰り返す
3. 0と1のどちらも残っていなければ受理する, そうでなければ拒否する

この動作時間をそれぞれ調べる

1. 左端から右端まで行って戻って来るため$2n = O(n)$
2. 一度0と1のペアを消すのに$O(n)$, これを最大で$n / 2$回繰り返す必要があるので$(n / 2)O(n) = O(n^2)$
3. 一度走査すれば良いため$O(n)$

以上をまとめると$O(n) + O(n^2) + O(n) = O(n^2)$となる.

言語のクラス分け

言語は, それを判定するために必要な時間計算量でクラス分けされる.

先程の$M_1$で判定した言語は$TIME(n^2)$となる.

$M_1$が判定する言語$A_1$を同じく判定するTuring機械$M_2$が作れ, それは$TIME(n \log n)$となる.

$M_2$はステップ2で0と1の総数の偶奇を調べ, 奇数なら拒否し, 偶数なら0と1を一つおきに消していく.

単一テープTuring機械ではこれ以上改良することは不可能である. 単一テープTuring機械で$o(n \log n)$時間で判定する任意の言語は正規言語であることが知られているが, $A_1$は正規言語ではないからである.