O記法 - What is it, naokirin?

O記法(big-oh notation) O(f (n))は入力された大きさに対して、実行時間が定数因子を除いてどのようになるかを表すことができる記法である。

というある種、物理的にも情報的にも見慣れた記法なんですが、今回はプログラム(アルゴリズム)でどのようにこのO記法であらわされる実行時間を計算するかを書いてみる。
もちろん、ガウディ本にのっとって、Ozをベースに話を進める。

核言語の文<s>の実行時間を示してみる。

<s>::=

　| local <x> in <s> end

skip	k
\| <x>1=<x>2	k
\| <x>=<v>	k
\| <s>1 <s>2	T(s1)+T(s2)
k+T(s)
\| proc {<x><y>1…<y>2 end	k
\| if <x> then <s>1 else <s>2 end	k+max(T(s1), T(s2))
\| case <x> of <pattern> then <s>1 else <s>2 end	k+max(T(s1), T(s2))
\| {<x> <y>1 … <y>n}	Tx(sizex(Ix({y1,…,yn})))

Ix({y1,…,yn})は、手続きの入力引数の集合を返す。
sizex({y1,…,yn})は手続きxの入力引数の大きさである。

これを用いて実行時間を計算する。
すると漸化式が出てくるのでそれを一般の入力の大きさnについて計算するとよい。

漸化式を解く方法は、簡単な数値を入れた場合の形から結果を推測し、漸化式にあてはめるという方法が一つ。
もう一つは母関数を使う方法がある。(昔拝んだ記憶がなくもない)

ここでよくある漸化式とその解を示す。