計算量入門

コンピュータアルゴリズムにおいて、計算量という値がある。
これはそのアルゴリズムの処理にどれくらいの計算コストが必要かということを表す。
領域計算量と呼ばれる必要なメモリの量を表すものもあるが、もっぱら計算量をというと時間計算量を表すことが多い気がする。

計算量の評価法

計算量の評価法としては、そのアルゴリズム１ステップにおいて行える処理を決め、実行回数を計測し、その結果を入力長の関数として表す。その関数の発散具合から評価を行う。

時間計算量の種類

時間計算量とは、名前の通り、その処理にどれくらいの時間(ループ)がかかるかということである。
最悪時間計算量、平均時間計算量、最善時間計算量という３種類の定義がある。
最善と平均に関しては、その評価が難しいためあまり実用的ではなく、最悪計算量が基本的に使われることが多い。アルゴリズムによっては平均を使う場合もある。

計算量の表記

評価法で計算量は入力長の関数として表せるとした。
実際に計算量を表記する時には、その関数がどのような関数で抑えれるかで記述する。
この時、O（ビックオー）を用いたビックオー記法で記述する。
単純な例を挙げると、1~nまでの数の順に足し合わせていくようなアルゴリズムでは、その計算量はnとなり
**O(n)**と表せる。

メモ

多項式時間認識可能な言語全体を表すPについて勉強している中での疑問とその説明
Pの例題として入力{x,y}が互いに素であるかの判定を行う時について考えた時、
x,yは共に２進数整数の時、データの入力長、つまり、
TMが入力された文字を読むのにかかる計算量はO(logx+logy)である。（この時底は２）
これはデータ入力長とデータの桁数とほぼ等しいという考えから導ける。
簡単のため、10進数の場合を考える。
x = 10000 = 10 ** 4 という入力が与えられた時、
それを表すにはn = log x = 4　だけ必要である。（ここで底は10）
つまり、一般に
10進数において入力長nの文字列を読み込むにはO(log10 n)だけかかる。
2進数において入力長nの文字列を読み込むにはO(log2 n)かかる。

未解消な疑問点として、TMでの四則演算などがPに属するのはなぜかという点が解消できていないので、解消出来次第追記します。