アルゴリズム [GRE CS]

「アルゴリズム」というのは、簡単に言ってしまえば、「何かをする手順」のこと。

そして、何かをするにしても、色々なやり方があり、どのやり方にも一長一短があり、もっと端的に、ある見方をすれば、あるやり方は他のやり方よりも優れている（ダメだ）という判断が下せる（こともある）。

アルゴリズムに関して、こうした優劣の判断は、大きく分けて「空間的効率」と「時間的効率」という2つの側面から為され、その中でも時間的効率ということを主に問題にすることが多い。というのも、アルゴリズムの優劣によって、同じ問題を特にしても、「劇的」と言ってもいいような差が出るからだ。

たとえば、今ここに1秒間につき1億回の演算が可能なプロセッサがあるとしよう。そして、何かあることを為そうというときの要素数nに応じて、n、n2、そして2nの処理数を要する3つのアルゴリズムがあるとする。このとき、処理にかける要素数によって、各アルゴリズムがその仕事を為し果せる時間は、以下のようになる。

	n	n2	2n
n=10	10-7秒	10-6秒	10-5秒
n=100	10-6秒	10-4秒	4×1014年

要素数nが10だと、どのアルゴリズムもマイクロ秒のオーダで処理が終わり、何てことはない。問題は、処理する要素数が増えるにしたがって、どれぐらい処理に要する時間が増えるか、ということで、nが100のときを見てもらうと……要素数nに対して処理がn秒とn2秒かかるアルゴリズムに関しては、まだマイクロ秒のうちに処理が終わるけど、処理に2n秒要するアルゴリズムは、な、何と、マイクロ秒どころか、単位からして「年」になっちゃってる。しかも、4×1014っつーんだから、これ、40兆年ですよ、40兆年。

斯様に、処理する要素数nが肩に乗っかった形で処理時間が表されるアルゴリズムは、「指数時間を要する」と言って、まあ、確かに、処理する要素数が小さい分には実用的だったり、何にせよ有限時間では処理は終わるし、端的に「解決不能」ではないんだけど……普通こういうのは「アルゴリズム」とは呼べないような代物。

で、アルゴリズムのこうした時間的効率（複雑さ）を計る指標として、O(ラージオー)記法というのとΩ(ラージオメガ)記法というのとΘ(ラージシータ)記法というのがあって、定義は以下の通り。

あるアルゴリズムの実行時間がその処理する要素数nの函数f(n)で表せ、それに対してある正の定数cとある正の定数n0が存在し、すべてのn≧n0に対してある函数g(x)が存在して、

　　0≦f(n)≦O(g(n))

　　0≦Ω(g(n))≦f(n)

　　0≦Ω(g(n))≦f(n)≦O(g(n))

と表せる場合、「（処理にf(n)かかる）あるアルゴリズムはO(g(n))（あるいはΩ(g(n))、Θ(g(n))）のオーダである」などと言う。

たとえば、あるアルゴリズムAの時間効率がf(x)=60n2+5n+1と表せる場合、60n2+5n+1≦60n2+5n2+n2=66n2だから、c=66とg(n)=n2すれば、O(n2)と表せ、ゆえに、アルゴリズムAの時間効率はO(n2)、というわけ。

さらに、60n2≦60n2+5n+1だから、このアルゴリズムのオーダはΩ(n2)でもあり、ゆえにΘ(n2)でもある。

そんな感じで、「仕込み」は終わりとして、次回からは色んなソートアルゴリズムを見てきましょ。