計算量を具体的に見てみる

アルゴリズムの話では、計算量の解析がかかせません。
計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。
こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。
ということで、やってみました。
計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。

O(1)

計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。

配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。
コードには入力量でのループが含まれません。

public class O1 extends ViewCompFrame{
    @Override
    void compute(int n) {
        proc();//なにか処理
    }

    public static void main(String[] args){
        new O1().init("O(1)", 1);
    }
}

O(log n)

計算時間がO(log n)になるアルゴリズムは、処理をひとつ行うたびに入力を何割か減らせるようなアルゴリズムです。入力が増えても計算時間がほとんど増えません。

二分探索が代表的なアルゴリズムです。
コードでは、ひとつ処理を行ったあと、入力を半分にして再起処理をするような場合です。

public class Olog extends ViewCompFrame{
    @Override
    public void compute(int n) {
        proc();//なにか処理
        if(n == 1) return;
        compute(n / 2);
    }

    public static void main(String[] args){
        new Olog().init("O(log n)", 1);
    }
}

次のような、繰り返し時にループインデックスを定数倍していくようなループを使う場合もあります。

    public void compute(int n) {
        for(int i = 1; i < n; i *= 2){
            proc();//なにか処理
        }
    }

四則演算も、桁数が大きくなるときは桁数の分だけ時間がかかるので、計算する値をnとすると計算時間のオーダーはO(log n)になります。

O(n)

計算時間がO(n)になるアルゴリズムは、入力の量だけ時間がかかるアルゴリズムです

入力をひとつひとつ処理する場合で多くの処理がこれにあたります。
たとえば整列されてない配列に要素が含まれているか探索する場合などがあります。

コードでは、n回繰り返すループがあります。

public class On extends ViewCompFrame{
    @Override
    public void compute(int n) {
        for(int i = 0; i < n; ++i){
            proc();//なにか処理
        }
    }

    public static void main(String[] args){
        new On().init("O(n)", 1 / 30.);
    }
}

O(n log n)

計算時間がO(n log n)になるアルゴリズムは、そのほとんどがソートを前処理として行います。

比較によるソートの計算量はO(n log n)より効率がよくならないことが知られています。
マージソートの計算量はO(n log n)になります。
コードは、次のように、入力全体の処理を、データを分割して再起呼び出しするようなものになります。

public class Onlog extends ViewCompFrame{
    @Override
    public void compute(int n) {
        for(int i = 0; i < n; ++ i){
            proc();//なにか処理
        }
        if(n == 1) return;
        compute(n / 2);
        compute(n - n / 2);
    }

    public static void main(String[] args){
        new Onlog().init("O(n log n)", 1 / 200.);
    }
}

けれども実際には、計算時間がO(n log n)になるような処理では、本質的な部分でこのようなコードを書くのではなくて、ソートを行ったあとで計算時間O(n)などの処理を行うものになります。
計算時間の違うアルゴリズムを複数並べるようなアルゴリズムの計算時間は、その中でもっとも効率が悪いアルゴリズムの計算時間になります。
O(n)とO(n log n)では、O(n log n)のほうが効率が悪いので、ソートを行ったあと計算時間O(n)の処理を行うようなアルゴリズムの計算時間はO(n log n)ということになります。

O(n^2)

計算時間がO(n^2)になるアルゴリズムは、要素からすべての組み合わせのペアについて調べるようなアルゴリズムです。

たとえば、平面上のいくつかの点から、一番距離が近い組み合わせを得る場合です。
コードでは、n回のループが2重になります。

public class On2 extends ViewCompFrame{
    @Override
    public void compute(int n) {
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < n; ++j){
                proc();//なにか処理
            }
        }
    }

    public static void main(String[] args){
        new On2().init("O(n ^ 2)", 1 / 3000.);
    }
}

O(2^n)

計算時間がO(2 ^ n)になるアルゴリズムは、要素を取り出すときのすべての組み合わせについて調べるようなアルゴリズムです。

たとえば次のような論理式を満たすように論理変数の値を決めるような問題があげられます。

(x1 & !x2 | x3) & (x4 | x3 & !x1) & (x2 & x5 & x6) & (・・・

データが増えるとすぐに計算時間が長くなってしまうので、現実的には計算不可能となってしまうことが多くあります。

コードは次のようになります。

public class O2n extends ViewCompFrame{
    @Override
    public void compute(int n) {
        if(n == 0){
            proc();//なにか処理
            return;
        }
        for(int i = 0; i < 2; ++i){
            compute(n - 1);
        }
    }

    public static void main(String[] args){
        new O2n().init("O(2 ^ n)", 1 / 3000.);
    }
}

単純に次のようにもかけます。

    @Override
    public void compute(int n) {
        long count = 2 << n;
        for(long i = 0; i < count; ++i){
            proc();//なにか処理
        }
    }

このことから、数値が与えられたときにその数値分ループを繰り返す場合、入力数値のビット数に対する計算量はO(2^n)ということになります。
たとえば、nビットの整数が与えられたとき、その整数より小さいすべての整数で割り切れるかどうか確認して素数判定を行うという場合です。

O(n!)

計算時間がO(n!)になるアルゴリズムは、要素の順番のすべての組み合わせを調べるようなアルゴリズムです。

代表的なものに、巡回セールスマン問題があります。巡回セールスマン問題は、いくつかの顧客を巡回して元の場所に帰るときに、どの順番で巡回すると一番移動距離が短いかを計算する問題です。また、囲碁の先読みを単純に実装するような場合も計算時間がO(n!)となります。

次のようなコードになりますが、このような計算時間のアルゴリズムは「計算が終わらない」ので、実際に書くことはあまりないと思います。

public class Ofact extends ViewCompFrame{
    @Override
    public void compute(int n) {
        if(n == 0){
            proc();//なにか処理
            return;
        }
        for(int i = 0; i < n; ++i){
            compute(n - 1);
        }
    }

    public static void main(String[] args){
        new Ofact().init("O(n!)", 1 / 3000.);
    }
}

計算時間がO(2^n)やO(n!)になるようなアルゴリズムを効率的に実装する場合は、厳密な解をもとめず近似解を求めるようにすることで、現実的に使えるようなアルゴリズムになります。

参考文献(2012/10/20追記)

計算量について、もう少し勉強したいと思ったら、まずは数学ガールがオススメです。

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

がっつり勉強したかったら、この本を。3分冊ですが、１冊あたりの実質ページ数が少ないので、却って読みやすいです。

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 2.計算可能性の理論
計算理論の基礎 [原著第2版] 3.複雑さの理論

描画プログラム

今回のプログラムを動かすには、このクラスが必要になります。

import java.awt.*;
import java.awt.geom.GeneralPath;
import java.awt.image.BufferedImage;
import javax.swing.*;

public abstract class ViewCompFrame extends JFrame{

    void init(String title, double range){
        setTitle(title);
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        setSize(408, 333);

        final BufferedImage img = new BufferedImage(
                400, 300, BufferedImage.TYPE_INT_ARGB);

        Graphics2D g = (Graphics2D) img.getGraphics();
        //g.scale(.75, .75);
        g.setRenderingHint(
                RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        g.setColor(Color.WHITE);
        g.fillRect(0, 0, 400, 300);
        g.setColor(Color.BLACK);
        g.drawLine(30, 30, 30, 280);
        g.drawLine(30, 280, 380, 280);

        GeneralPath gp = new GeneralPath();
        for(int i = 1; i < 350; ++i){
            count = 0;
            compute(i);
            int c = (int) (count * 30 * 250 / 350 * range);
            int y = 280 - c;
            if(i == 1){
                gp.moveTo(i + 30, y);
            }else{
                gp.lineTo(i + 30, y);
            }
            if(y < 0) break;
        }
        g.setStroke(new BasicStroke(2));
        g.setColor(Color.RED);
        g.draw(gp);
        g.dispose();

        add(new JComponent() {
            @Override
            protected void paintComponent(Graphics g) {
                g.drawImage(img, 0, 0, ViewCompFrame.this);
            }
        });
        setVisible(true);
    }

    private int count;
    void proc(){
        ++count;
    }

    abstract void compute(int n);
}