きしだのはてな このページをアンテナに追加 RSSフィード

2009-01-06(火) 計算量を具体的に見てみる

[]計算量を具体的に見てみる 18:25 計算量を具体的に見てみる - きしだのはてな を含むブックマーク

アルゴリズムの話では、計算量の解析がかかせません。

計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。

こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。

ということで、やってみました。

計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。


O(1)

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

f:id:nowokay:20090106164543p:image


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

コードには入力量でのループが含まれません。

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)になるアルゴリズムは、処理をひとつ行うたびに入力を何割か減らせるようなアルゴリズムです。入力が増えても計算時間がほとんど増えません。

f:id:nowokay:20090106164546p:image


二分探索が代表的なアルゴリズムです。

コードでは、ひとつ処理を行ったあと、入力を半分にして再起処理をするような場合です。

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)になるアルゴリズムは、入力の量だけ時間がかかるアルゴリズムです

f:id:nowokay:20090106164548p:image


入力をひとつひとつ処理する場合で多くの処理がこれにあたります。

たとえば整列されてない配列に要素が含まれているか探索する場合などがあります。


コードでは、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)になるアルゴリズムは、そのほとんどがソートを前処理として行います。

f:id:nowokay:20090106164542p:image


比較によるソートの計算量は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)になるアルゴリズムは、要素からすべての組み合わせのペアについて調べるようなアルゴリズムです。

f:id:nowokay:20090106164547p:image


たとえば、平面上のいくつかの点から、一番距離が近い組み合わせを得る場合です。

コードでは、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)になるアルゴリズムは、要素を取り出すときのすべての組み合わせについて調べるようなアルゴリズムです。

f:id:nowokay:20090106164544p:image


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

(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!)になるアルゴリズムは、要素の順番のすべての組み合わせを調べるようなアルゴリズムです。

f:id:nowokay:20090106164545p:image


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

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


がっつり勉強したかったら、この本を。3分冊ですが、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);
}

平田敦平田敦 2009/03/18 16:29 きしださん、いつも良エントリをありがとうございます。
技術評論社のコンテンツサイト gihyo.jp で掲載させていただいている連載「はじめMath!Javaでコンピュータ数学」で、計算量に関する回を持ちたいと思っています。
このエントリの記述を参考にさせていただきます!
もし、問題がありましたら、おっしゃってください。
よろしくお願いいたします。

nowokaynowokay 2009/03/18 18:05 ブログで書かれてたのを見ました(^^
発想の元になったのは「アルゴリズムデザイン」という本なので、そちらも参考に。

いまこのエントリ読み返すと、よくこんなこと思いついたなぁと思います。

2008-11-11(火)

ポウラナー ヘフェ ヴァイスビア

[][]longで指定範囲の乱数 16:29 longで指定範囲の乱数 - きしだのはてな を含むブックマーク

結局、乱数が一様であれば、それを分割した部分も一様になるはずなので、基本的にはgetLong() % nで大丈夫そうです。ただ、そうするとlongの範囲が割り切れなかった部分で、乱数にムラができるので、考慮する必要があります。

で、結局そうすると、nがintの範囲ならgetInt(n)を使って、intの範囲を超えていればgetLongでn以上のものを捨てれば大丈夫じゃないかということになりました。

なので、結局こんな感じになります。

public long nextLong(Random r, long n){
    if(n <= Integer.MAX_VALUE) return r.nextInt((int)n);
    for(;;){
        long t = r.nextLong();
        if(t < 0) t -= Long.MIN_VALUE;
        if(t < n) return t;
    }
}

ということをquintiaさんから教えてもらいました。java.util.Randomですべてのlongが生成できないという問題は、メルセンヌ・ツイスターで解決。

http://materia.jp/blog/20081110.html#p02


追記。なんか勘違いがありました。結局、nextInt(int)と同じことをやればよいだけでした。

long nextLong(long n){
  long bits, value;
  do{
    bits = r.nextLong();
    if(bits < 0) bits -= Long.MIN_VALUE;
    val = bits % n;
  } while (bits - val + (n - 1);
  return val;
}

[][]フェルマーテストで素数判定 16:29 フェルマーテストで素数判定 - きしだのはてな を含むブックマーク

longの乱数が欲しかったのは、素数判定がやりたかったからなのですが、確認のためにエラトステネスの篩との比較をしたので、結局intの範囲までしか使いませんでした。

素数判定には、フェルマーテストを使います。で、今回は、わざと判定回数を少なくしてみて誤判定させています。

そうすると、こんな感じの実行結果になりました。

1729が素数と誤判定

8911が素数と誤判定

29341が素数と誤判定

46657が素数と誤判定

52633が素数と誤判定

75361が素数と誤判定


なんどか実行すると、誤判定が起きる数はいくつかに決まっていることがわかります。

この数は、カーマイケル数といいます。計算上で素数のようなふるまいをするので、擬素数ともいいます。


ソースはこんな感じ。

import java.util.Random;

public class PrimeCheck {
    public static void main(String[] args){
        r.nextLong();
        boolean[] comp = eratos(100000);
        for(int i = 9; i < comp.length; i += 2){
            if(fermatCheck(i, 8) == comp[i]){
                System.out.printf("%dが%sと誤判定%n", i, comp[i] ? "素数" : "合成数");
            }
        }
    }

    static Random r = new Random();

    /** エラトステネスの篩により合成数ならtrue/素数ならfalseの配列 */
    private static boolean[] eratos(int n){
        boolean[] ret = new boolean[n + 1];
        ret[0] = true;
        ret[1] = true;
        for(int i = 4; i <= n; i += 2){
            ret[i] = true;
        }
        for(int i = 3; i <= n; i += 2){
            if(ret[i]) continue;
            for(int j = i * 2; j <= n; j += i){
                ret[j] = true;
            }
        }
        return ret;
    }

    /** フェルマーテストによる素数判定 素数:true 合成数:false */
    private static boolean fermatCheck(int n, int c){
        for(int i = 0; i < c; ++i){
            if(n % 2 == 0) return false;//偶数なら合成数
            int a = r.nextInt(n - 2) + 2;//2以上n未満の値
            int g = (int) gcd(n, a);
            if(g != 1) return false;//最大公約数がみつかったなら合成数
            if(modPow(a, n - 1, n) != 1) return false;
        }
        return true;
    }

    /** (a ^ b) % m を計算 */
    static int modPow(int a, int b, int m){
        if(a == 0) return 0;

        int result = 1;
        a %= m;
        while(b != 0){
            if(b % 2 == 1){
                result = (int)(((long)result * a) % m);
            }
            a = (int)(((long)a * a) % m);
            b = b >> 1;
        }

        return result;
    }

    /** 最大公約数を求める(a > b) */
    private static long gcd(long a, long b){
        if(b == 0) return a;
        long m = a % b;

        return gcd(b, m);
    }
}

ちなみに、gcdやmodPowはBigIntegerに実装があるので、これを使うこともできますが、かなり遅くなります。まあ、それを言ってしまえば、確率的素数判定のメソッドisProbablePrimeというのもあるわけですが。

とりあえず、BigIntegerのメソッドを使うと、こうなります。

    private static boolean fermatCheck(int n, int c){
        for(int i = 0; i < c; ++i){
            if(n % 2 == 0) return false;//偶数なら合成数
            int a = r.nextInt(n - 2) + 2;//2以上n未満の値
            BigInteger ba = BigInteger.valueOf(a);
            BigInteger bn = BigInteger.valueOf(n);
            int g = bn.gcd(ba).intValue();
            if(g != 1) return false;//最大公約数がみつかったなら合成数
            if(!ba.modPow(bn, bn).intValue().equals(ba)) return false;
        }
        return true;
    }

everpeaceeverpeace 2008/11/12 12:39 0,1を出力する議事乱数生成器があればその64回分を1出力ととらえればlongっぽいのが作れるのではないでしょうか(質は落ちますが)。

nowokaynowokay 2008/11/12 17:05 longはgetLongで作れるのですが、たとえば4321億5432万6543までという風に指定した範囲の整数を等確率で生成したかったのです。

nowokaynowokay 2008/11/12 17:33 けど、この方法だと、21億より少し多い数だと、範囲内の数値が出る確率が21億分の1になってしまいそうな気が。もう少し考えてみよう。

nowokaynowokay 2008/11/12 21:27 勘違いがあった ><

2008-07-20(日)

トリプルカラメリート

[][]こんなプログラムを作ったけど 17:42 こんなプログラムを作ったけど - きしだのはてな を含むブックマーク

こないだの問題。

http://d.hatena.ne.jp/nowokay/20080717


Javaで書くとこんな感じか。

public class SBH {
    public static void main(String[] args){
        sbh(new String[]{"BAB", "ABA", "AAB", "AAA", "BAA"});
        sbh(new String[]{"BAB", "AAB", "AAA", "BAA"});
        sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "BCA", "CAB"});
        sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB"});
        sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB", "CAB", "BBC"});
    }
    
    public static void sbh(String[] strs){
        System.out.print("{");
        List words = new ArrayList();
        for(String str : strs) words.add(str);

        for(String start : strs){
            List wordscpy = new LinkedList(words);
            wordscpy.remove(start);
            sbh_impl(start, wordscpy);
        }
        System.out.print("}");
    }

    private static void sbh_impl(String str, List<String> words){
        if(words.size() == 0){
            //答えがでてる
            System.out.print(str + " ");
            return;
        }
        for(String s : words){
            if(!str.substring(str.length() - s.length() +1).equals(
                    s.substring(0, s.length() - 1))) continue;
            List wordscpy = new LinkedList(words);
            wordscpy.remove(s);
            sbh_impl(str + s.substring(s.length() - 1), wordscpy);
        }
    }
}

これで、こんな感じになる。

{BABAAAB BAAABAB }

{}

{CAABABCAB CAABCABAB CABABCAAB CABCAABAB }

{}

{}


ようするに、連結できるすべての組み合わせを見て、最後までたどり着けたら結果として出力。

permutationって、リストのすべての順列を求めるような関数がある環境の人は、それを使ってできたリストの連結性を検査して、全部つながったらOKみたいな感じでやってますね。


[][]これを線形時間で解くには 20:45 これを線形時間で解くには - きしだのはてな を含むブックマーク

さて、これで求めたい文字列が得られたわけですが、ここでアルゴリズムとして全ての順列について検査しているので、計算時間がO(n!)になってしまいます。

そこで、これを線形時間、つまり、入力文字列数nと出力文字列数mに比例した計算時間O(mn)になるようにしたい。


ということで、与えられた文字列

{"CAA", "AAB", "ABA", "BAB", "ABC", "BCA", "CAB"}

から、次のような、k-1文字の部分文字列の遷移を書いてみます。

f:id:nowokay:20080720203616p:image

そうすると、答えになるのは、このグラフが一筆書きできるもの、つまりオイラーパスを求めればいいということになります。そうなると、あとは一般的なグラフの問題として解くことができます。


で、この問題っていったいなんだったのかというと、バイオインフォマティクスでDNAの配列を決めるための問題で、Sequence By Hybridization(SBH)といいます。

実際のところ、測定誤差があることから、このアルゴリズムはそのままでは使いものにならないようですが、まあ、こんな考え方がベースになっているということです。


実際組もうと思ったのだけど、全ての組み合わせを線形時間で求めようとしたらめんどくさかったので、答えを一組だすものを作ってみました。

public class SBH {
    public static void main(String[] args){
        System.out.println(sbh(new String[]{"BAB", "ABA", "AAB", "AAA", "BAA"}));
        System.out.println(sbh(new String[]{"BAB", "AAB", "AAA", "BAA"}));
        System.out.println(sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "BCA", "CAB"}));
        System.out.println(sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB"}));
        System.out.println(sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB", "CAB", "BBC"}));
    }
    
    public static String sbh(String[] s){
        String result = "";
        if(s == null || s.length == 0) return result;
        //出る側のmatrix
        Map<String, Set<String>> matrix = new HashMap<String, Set<String>>();
        //入る側のmatrix
        Map<String, Set<String>> invmatrix = new HashMap<String, Set<String>>();
        //出入りグラフの行列を作成
        for(String str : s){
            String from = str.substring(0, str.length() - 1);
            String to = str.substring(1);
            if(!matrix.containsKey(from)) matrix.put(from, new HashSet<String>());
            matrix.get(from).add(to);
            if(!invmatrix.containsKey(from)) invmatrix.put(from, new HashSet<String>());
            if(!invmatrix.containsKey(to)) invmatrix.put(to, new HashSet<String>());
            invmatrix.get(to).add(from);
        }
        //オイラーグラフ(一筆書きできる)かどうか判定
        String outover = null;//出が超過してる
        String inover = null;//入りが超過してる
        for(String key : invmatrix.keySet()){
            int outcount = matrix.containsKey(key) ? matrix.get(key).size() : 0;
            int incount = invmatrix.get(key).size();

            if(outcount == incount){
                //出入りが同じ数
            }else if(outcount == incount + 1){
                if(outover != null){
                    //出 > 入が2つ以上あるとオイラーグラフではない
                    return result;
                }
                outover = key;
            }else if(outcount + 1 == incount){
                if(inover != null){
                    //出 > 入が2つ以上あるとオイラーグラフではない
                    return result;
                }
                inover = key;
            }else{
                //出と入の差が2以上あるとオイラーグラフではない
                return result;
            }
        }
        if((outover != null) != (inover != null)) return result;
        
        //オイラーパスを探索
        List<String> results = new LinkedList<String>();//結果
        List<String> temp = new LinkedList<String>();
        //出が多いところがあれば、そこから。そうでなければ閉路なのでどこからでもいい
        String word = (outover != null) ? outover : matrix.keySet().iterator().next();
        result += word.charAt(0);
        int insertindex = 0;
        while(matrix.size() > 0){
            temp.add(word);
            
            if(!matrix.containsKey(word)){
                //次がないばあいは、適当なところから始めて連結させる
                results.addAll(insertindex, temp);//厳密に線形にするときは、ここを工夫
                temp.clear();
                String next = matrix.keySet().iterator().next();
                insertindex = results.indexOf(word);//厳密に線形にするときは、ここを工夫
                word = next;
                continue;
            }
            
            String next = matrix.get(word).iterator().next();
            matrix.get(word).remove(next);
            if(matrix.get(word).isEmpty()) matrix.remove(word);
            word = next;
        }
        temp.add(word);
        results.addAll(insertindex, temp);
        //答えを作成
        for(String str : results) result += str.charAt(1);
        return result;
    }
    
}

とおりすがりとおりすがり 2008/07/21 01:27 SBHってどうみてもソフトバンクホークスでしょw

nowokaynowokay 2008/07/21 03:49 だ〜っ、書くの我慢してたのに

2008-07-17(木)

ヒューガルデンホワイト

[]こんなプログラムを書いてみよう 20:37 こんなプログラムを書いてみよう - きしだのはてな を含むブックマーク

文字列の集合{ BAB, AAB, BAA, AAA, ABA }があるとき、これらのすべてを1回ずつ含み、かつ、3文字の部分文字列としてはこれらの文字列しか含まない文字列は、BABAAABとBAAABABの2通りある。

文字列の集合が{ BAB, AAB, BAA, AAA }のときは、そのような条件では文字列が作れない。


ということで、こういう感じで3文字の文字列がいくつか与えられたとき、それらを全部使いつつ、与えられてない3文字が現れないような文字列を求めるプログラムを作る。

とりあえず{ ABA, BAB, ABC, BCA, CAB, CAA, AAB } がテストデータ。4通り作れるはず。ここからBCAを外すと作れなくなるはず。


追記:できたら、4文字版、5文字版・・・k文字版を

追記2:簡単にできちゃったら、計算時間が線形時間、つまり入力文字列数と答の数に比例した時間で計算できるようにすると、難しめになるんじゃないでしょか

koichikkoichik 2008/07/18 05:00 コメント欄で失礼.Prolog でやってみたよ (k 文字版).

nowokay(List, Result) :-
 permutation(List, [X|Xs]),
 nowokay2(Xs, X, Result).

nowokay2([], Atom, Atom).
nowokay2([X|Xs], Atom, Result) :-
 sub_atom(X, _, 1, 0, Sub2),
 atom_concat(Atom, Sub2, Atom2),
 sub_atom(Atom2, _, _, 0, X),
 nowokay2(Xs, Atom2, Result).

?- findall(X, nowokay([aba, bab, abc, bca, cab, caa, aab], X), R).
R = [cababcaab, cabcaabab, caababcab, caabcabab].

?- findall(X, nowokay([aba, bab, abc, cab, caa, aab], X), R).
R = [].

ともあれ (JW),自分といい大森さんといい permutation を自作しないのは手抜きじゃないかという気のせいが.(^^;

nowokaynowokay 2008/07/18 13:44 permutation!そんな便利なものが!

2008-03-08(土)

[][]凸包を求める - jarvisのマーチ 06:04 凸包を求める - jarvisのマーチ - きしだのはてな を含むブックマーク

凸包を求めるアルゴリズム、最後にjarvisのマーチという方法をやってみます。

考え方としては、まず最初にy座標が一番小さいものを選んで、その点からの角度が一番小さい点を選んでいきます。

f:id:nowokay:20080309235143j:image

角度は内積で求めます。


このアルゴリズムの場合、凸包上の頂点ごとに点の数の繰り返しを行うので、点の数n、頂点数hとすると、計算量はO(hn)になります。

    static List<Point> points = new ArrayList<Point>();
    static List<Point> hull;
    
    static void createConvexHull(){
        //Y座標で並べ替え
        Collections.sort(points, new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Point)o1).y - ((Point)o2).y;
            }
        });
        
        //凸包を求める
        hull = new ArrayList<Point>();
        //一番上の点を求める
        Point first = points.get(0);
        hull.add(first);
        int vx = 1;
        int vy = 0;
        Point oldpoint = first;
        for(;;){
            //前回の辺との角度が一番小さい点を求める。
            Point minpoint = null;
            int minvecx = 0;
            int minvecy = 0;
            double maxcos = -1;
            for(Point p : points){
                if(p == oldpoint) continue;
                int ox = p.x - oldpoint.x;
                int oy = p.y - oldpoint.y;
                //角度を求める
                double cos = (ox * vx + oy * vy) / 
                        (Math.sqrt(ox * ox + oy * oy) * Math.sqrt(vx * vx + vy * vy));
                if(cos > maxcos){
                    //いままでの中で一番角度が小さいとき
                    maxcos = cos;
                    minvecx = ox;
                    minvecy = oy;
                    minpoint = p;
                }
            }
            if(minpoint == first){
                //最初の点に戻ったら終わり
                break;
            }
            vx = minvecx;
            vy = minvecy;
            oldpoint = minpoint;
            hull.add(minpoint);
        }
    }

前川前川 2017/06/16 04:34 「角度が一番小さい点」が複数ある場合の処理は?