アルゴリズムの基礎

アルゴリズムとは？

あるデータを集めてきて統計学者さんなんかに見せるとそこから色々な情報を提供してくれます。
ではこれが「学者」みたいな人ではなく、手続き―つまり、このようにすれば持ってきたデータから所望のデータを得られるという手順―のことをアルゴリズムと言います。

以下では種々の用語を定義していきます。
1)入力(input)・・・アルゴリズムに与えるデータのこと。学者の例で言えば集めたデータ。
2)出力(output)・・・アルゴリズムから得られるデータ。
3)入力の大きさ(input size)/問題の大きさ(problem size)・・・与える入力データの数のこと。

アルゴリズムの優劣

入力をいれて出力を取り出すこの「アルゴリズム」というのは非常に広範な概念です。
たとえば、「１～１００までの数を入力して、その合計を出力する」といったようなアルゴリズムを考えることができます。

さて、これを解くための最も堂々たる単純な方法はすべて足しあげることですね。
1+2+3+…=？
少なくとも手計算で流行りたくないですね。これを簡単に計算する方法として有名（？）な次の方法があります。

1)一番小さい数と一番大きい数を足し合わせる。この和をXとする。(この場合 X=1+100=101)
2)この数は「k番目に小さい数とk番目に大きい数を足し合わせた数」として一般化できる。(例えばk=3ならば 3+98=101でXと同じ数になる)
3)よって、入力の数nの半分 n/2 個の組み合わせの和がすべて1)で求めた数Xになるので、が求める答えになる。(n=100なので、101×100/2=5050が答え)

さて、初めの地道に足し合わせる方法と、上の方法、どちらが「優秀」なアルゴリズムかというのは言うまでもないと思います。
このように、ある結果を求めるためにどの程度計算が必要なのか、という指標を計算量と言います。

オーダーという概念

前節のことをまとめれば「計算量が少ないほど、そのアルゴリズムは優秀」ということになります。
しかし、たとえば「4個の数を地道に足しあげる」のか「5000個の数を『優秀』な方法で足しあげる」のか、どちらが早いかといわれるといくら「優秀」なアルゴリズムでも負けてしまいそうです。

直感的にも明らかですが、アルゴリズムの計算量というのは入力の数nが増えれば増える程増加する場合がほとんどです。
（nが増えても計算量が変わらないことはありますが、少なくとも計算が簡単になることはないでしょう。）
ですからただ単に計算量が多いか少ないかではなくて、「nが増えることによってどの程度計算量が大きくなるのか」ということで考える方が、よりいい指標になりそうです。

そこで次の定義があります。
[定義]関数および任意の実数$a$に対して

が成立しているとき

と表記する。またfはgで押さえられているといったり、fはgのオーダーであると言ったり。
さらに、ここで使われた記号のをランダウの記号と言います。

要するに「単純に計算量だけで比較しちゃダメ」だということだから、入力に対する「関数」と比較してしまえ、ということです。

複雑度

さて、今までは計算量だけで物事を考えてきましたが、計算機でアルゴリズムを動かす時にはもう一つ『容量』の概念が重要です。
入力nが増えるにしたがって爆発的にメモリを食ってしまうような計算はいくら早くても稼働させることができないからです。

ここで以上の２つのアルゴリズムに関する指標、計算量のオーダーの事を時間複雑度(time complexity)、記憶容量のオーダーのことを空間複雑度(space complexity)と言います。
またこれらを合わせて複雑度(complexity)といいます。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。