あなたが一番好きなアルゴリズムを教えてください。

クイックソートが好きです。

異様に件数が多い対象の整列に、いかに高速であるかを身をもって思い知りました。

（ヒープソートはメモリが足りないです。。。）

あと、ハッシュアルゴリズムのSHA-1も好きですね。

CRYPT暗号のアルゴリズムも好きです。

こう考えると、自分で実際にプログラムを書いて有用性を確認したアルゴリズムは大抵好きな気がします。。。

再帰・・・自分自身を使って自分を定義する

プログラムを勉強したてのころに、ハードディスクの中の全てのMP3ファイルを調べてリスト化するコードを書こうとしていました。

ところが特定のフォルダの中のMP3は取得できるのですが、そのサブフォルダ更にそのサブフォルダと続く階層がどこまで続くのかがわからないので、どう書けばいいのかがわからず一度挫折しました。

しばらくして、アルゴリズムの本を読んでいたときに再帰というのがあるということを知りました。そのとき直感的にこれを使えば前に諦めたコードが書けると思い、書いてみると実際すごくシンプルなコードで実現できることがわかりました。

ネットなどで調べれば方法はすぐにわかったのかもしれませんが、プログラムということの面白さの本質は自分で考えることなんだと再帰を通して理解できました。

グラフアルゴリズム (グラフ理論的アルゴリズム)，特にグラフのトポロジカルな構造を解析するアルゴリズムに一番興味があります．(単に量的な最適化を行うだけのアルゴリズムにはそれほど興味がない．)

例えば，

• 経路探索 (最短，最長，ハミルトン路/閉路，オイラー路 (一筆書き)，スパニングツリーなど)
• 無向グラフの非可分成分検出 / 有向グラフの強連結成分検出

好きな理由は，局所的で単純な情報を積み重ねて全体的な構造や性質を認識できるところ．

(グラフアルゴリズムを知らないプログラマから見れば，どうしてそんなことができるのか不思議に思うだろう．ただ非プログラマには，「それができることがすごい」ということさえわからないだろうけど．)

応用分野としては，プログラムの解析 (データフロー解析，制御フロー解析，(コンパイラなどによる) 最適化，プログラムスライシング，バグ検出など) に最も興味があり，暇ができたら趣味でプログラム解析ツールとか逆コンパイラなどを作ってみたいと思っているのですが … 最近全く暇がない．orz

昔，ループ (サイクル) が複雑に入り組んだグラフを解析するアルゴリズムを考えたことがあります．これだと現在の制御フロー解析で使われている，ドミネーターツリーを使う方法に比べて goto 文だらけのスパゲッティプログラムも解析できる可能性があるし，制御系解析に応用すれば多入力・多出力・多重フィードバックループの構造も解析できるはず．数学的に計算量などは証明していないけど，たぶん O(n²) ぐらい？

でも，当時勤めていた某大手電機メーカの研究所で周囲にその話をしても，アルゴリズムの内容どころか応用的価値さえ全く理解してもらえず「それが何の役に立つの？」と言われた…．○|￣|＿

さらに，グラフのトポロジカルな構造が時間的に変化するシステム (グラフ書き換えシステムなど) にも昔から興味があって，その変化を解析するアルゴリズムも考えてみたいけど，いまだに具体的な応用問題を扱う機会がありません．orz

あと，幾何学や計算幾何学のアルゴリズムも非常に興味があります．幾何学アルゴリズムという言葉が出たついでに余談ですが，「外積 Ｃ言語」とか「外積 アルゴリズム」などで検索して私のサイトにやってくる人が後を絶たないのが激謎．外積の計算式って，単純な掛け算と引き算だけ (Ax * By - Ay * Bx) なのに，一体何がわからないのかわからない．

「どんな言語であれ，"Hello, world!" と四則演算の書き方がわかれば小学生でもすぐ書けるでしょ！」と言いたい．それと，大学生以上でも三角形の重心の公式を知らない人が多いようで，「三角形 重心 公式 (Ｃ言語)」などで検索して来る人も多い．

Combsort 11。

バブルソートにほんの少し手を加えるだけで、劇的に速くなるのに驚きました。

昔あった日系バイトで紹介されて知りました。

コーディングも簡単なので、実装して使ったことがあります。

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%A...

http://www.avis.ne.jp/~g-k-toys/hanoi01.html

3番目の方が再帰を挙げているので若干かぶってしまいますが、

一番感動したのは「ハノイの塔」を解くアルゴリズムです。

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

このパズルを解くための、再帰を用いたアルゴリズムとして有名なものですが

最初に知ったときはその発想に驚いたものです。

• 8枚の円盤を動かしたいなら、上から7枚をどこかに移動させておいて最後の1枚を空き場所に移動させればいい
• 7枚の円盤を動かしたいなら、上から6枚をどこかに移動させておいて最後の1枚を空き場所に移動させればいい
• ……
• 2枚の円盤を動かしたいなら、上から1枚をどこかに移動させておいて最後の1枚を空き場所に移動させればいい
• 一番上の円盤は自由に移動させられる

と、どんどん問題を細かくしていって大きな問題を解決するというところがとても好きです。

連立一次方程式を反復的に解く方法の一つConjugateGradient法が好きです。

行列-ベクトル積やベクトル同士の内積など簡単な操作を反復するだけで、反復数だけの大きさの基底で張られる空間の中から厳密解に作用素ノルムで最も近い解を見つけてくれます。毎反復ごとに大量の基底から最適解を探しているはずなのに、メモリ上にその基底を保存する必要がないのでメモリコストが小さく高速なのが非常に魅力的です。このアルゴリズムで使われている数学も面白いです。

20世紀アルゴリズムTop10にも選ばれています。

初めて見た時、こんな適当な方法でいいのか？と思ったのが

乱数を生成する、線形合同法です。

これ以上ないほど簡単な仕組みなのに、C言語のrand関数はこのアルゴリズムと聞いて驚いたとともに、なんとなく親しみを感じた記憶があります。

マニアックなところだと、BloomFilterはちょっと感動しました。

どうやったって１万個のオブジェクトの有無を表すには一万個の変数が必要だろ、と思ってた私には、

（無いものを有るという）覚え違えはするかもしれないけど5000個で十分だよ、という新しい視点がかなり新鮮でした。

「考えた人頭いいなー」という点でデータ圧縮で用いられているアルゴリズム.

LZ法など, 理論的に見てもいろいろ面白かったりします.

少しズレてるかもしれませんが、SQLで木構造を構築する為に使う「入れ子集合モデル」のアルゴリズムが好きです。

SQLは基本的にツリーとの相性が悪いですが、ツリーを表現する方法として左、右のインデックスで集合を表す事によってSQLでも簡単にツリーの表現を行う事ができるようにしている部分がすばらしいです。

直感的に理解できるデータと簡単な記述によってツリー表現を行える点が個人的に好きな理由です。

http://www.geocities.jp/mickindex/database/db_tree_ns.html

ミニマックス法にはお世話になりました。

ブロックソート

好きと言うより、Wikipediaのわかりやすい解説見てもイマイチ理解できないあたりがステキ。

ソートの話で思い出したことがあるので，再度失礼します．

一番速いソートは O(n * log(n)) だと思っている人も多いんじゃないかと

思いますが，O(n * k) (k：キーの平均長) とか O(n) というアルゴリズムも

存在します．

とりあえず原理だけを手っ取り早く理解したい人は

↓の回答 #4 を参照．(小学生でもわかるうまい説明)

OKWave QNo.2778735：アルゴリズムについて教えてください

http://okwave.jp/qa2778735.html

基数ソート (Wikipedia)

http://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E3%82%BD%E3%83%B...

↓英語版の方が断然詳しく書いてます．読んでないけど．(^^;

Radix sort (Wikipedia)

http://en.wikipedia.org/wiki/Radix_sort

バケットソート (Wikipedia)

http://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%8...

Bucket sort (Wikipedia)

http://en.wikipedia.org/wiki/Bucket_sort

最速であるにもかかわらず，あまり知られていない理由は，メモリを大量に

必要とすることと，整数型以外のキーでは実装しにくいからでしょうねぇ…．

┌─これに関連して私が23年ほど前に驚嘆した話と，もう一つ面白いアルゴリズム

↓ (大量のメモリを初期化せずに使用する方法 (ただし用途は極めて限定的)) の話．

OKWave QNo.2722011：アルゴリズムの名前を教えてください

http://okwave.jp/qa2722011.html

名前を知らないのですが「長さnの配列の要素をk個ローテートする」方法を初めて知ったときには驚きました。

1. 先頭からk個を逆順にする。
2. 残りn-k個を逆順にする。
3. 全体(n個)を逆順にする。

この方法の最大のメリットは、テンポラリのバッファを用意する必要が無いという点です。

http://aggregate.org/MAGIC/

このサイトに載ってるビット演算を駆使したアルゴリズムと最初に出会ったときは感動しました．特に感動したのが，1であるビットの個数を求める Population Count です．

http://aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count...

また，SALINGER さんが回答3で再帰を挙げらっしゃいますが，私も同様に再帰を挙げたいと思います．とくに単なる再帰ではなくて，末尾再帰ですかね．これがループに変換できるという最適化には感動しました．

http://practical-scheme.net/docs/tailcall-j.html

再帰つながりで Y Combinator も挙げさせていただきます．「関数適用の不動点」を考えることが，こんなにも世界を楽しくさせるなんて感動ですよね．

http://en.wikipedia.org/wiki/Y_combinator

虱潰し法 (brute force search)です。

http://en.wikipedia.org/wiki/Brute-force_search

応用範囲が非常に広い

バグが出にくい

コンピュータがガリガリ動いているのを見ているのは楽しい

ので大好きです。

BM法という文字列検索に驚きました。

http://ja.wikipedia.org/wiki/BM%E6%B3%95

テキストエディタの文字列検索などで使うものもあり、

単純にテキストの先頭から検索したい文字列を

比較する場合に比べ、検索速度に明確な差が出ます。

特筆すべきは、検索したい文字列が長くなれば

長くなるほどスピードが上がるという点です。

↓の本を読み、まさか、とは思い、

実際にコードを書いてみて実際にそのスピードが

出るものですから、大変感動したものです。

このアルゴリズムは↓の本

『C言語による最新アルゴリズム事典』で見つけたものです。

http://www.amazon.co.jp/C%E8%A8%80%E8%AA%9E%E3%81%AB%E3%82%88%E3...

この本には他にも今も役に立つアルゴリズムが

嫌というほど載っていますので、絶対買って

損はないとおもいます。

ただ、この当時だとGoogleというものがなく（笑）

当然、全文検索で世界中のテキストを一瞬に

検索できるようになるとは到底思うところでは

ありませんでした。

技術の進歩にただただ驚かされるばかりです。

アルゴリズムの世界は広くて、新しいものに出会うたびに感心しっぱなしなので「一番」を選ぶのは難しいですが、最近知って感動したのはこれです(知ってる人は昔から知っていたと思いますが)。IEEE単精度浮動小数点数xに対して 1/√x の良い近似値を計算します。

float InvSqrt(float x)
{
  float xhalf = 0.5f*x;
  int i = *(int*)&x;
  i = 0x5f3759df - (i>>1);
  x = *(float*)&i;
  x = x*(1.5f-xhalf*x*x);
  return x;
}

最近のCの規格だと *(int*)&x 等はunionを使わないと最適化に対して安全ではないかもしれません。

原理はNewton-Raphson法の近似を一回まわしているだけなんですが、初期値の設定の部分がものすごく巧みです。詳しい解析はこちら。

http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

このコードを誰が最初に考えたかを追ったこの記事も面白いです。

http://www.beyond3d.com/content/articles/8/

線形計画法に出てくる「双対問題」とか「主・双対単体法」。そんなうまい話ってあるもんなんだなー、と。

Danzigが見つけたのかなーと思ってWikipedia見てみたら、von Neumannが予想して証明はTucker、ただし同年にDanzigも独立に証明って書いてました。

ニュートン法

http://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%A5%E3%83%BC%E3%83%8...

大学の電算の授業で最初に習ったかな。今でも覚えてる。言語はFortranだった。

自動調整プログラムで最適解を求めるのに使った。

圧縮接尾辞配列(compressed suffix array)

http://tcslab.csce.kyushu-u.ac.jp/~sada/lectures/AlgoEng11.ppt

http://hillbig.cocolog-nifty.com/do/files/practical_compressed_i...

ゲノム配列全体の全文検索システムを作ろうとしたときに見つけました。

索引が原文よりも小さくなる（こともある？）など良い性質を持っているようです。

索引をいかに高速に、省メモリで作るかなどで

ジョルダン閉曲線と任意点の相対位置を判別するアルゴリズム。

（簡単に言い直すと、点が輪の中に有るか、線上か、外に有るかを判別する）

私がサブルーチンを組んだのですが、IBMのサブルーチンより早かった（Logicが異なる）

単純に言えば、X又はYで直線を引き、曲線との交点の数が奇数か偶数で判定するわけです。(線上やS字、U字に近い部分は判定が少し複雑になりますが）兎に角人間が見ても分かり易いロジックです。それをコンピュータのプログラムかしたものです。

FFT（高速フーリエ変換）

デジタル信号の基礎技術。

フーリエ級数だけでも、数学としては面白いですけどね。

Shorの因数分解アルゴリズム

http://www.senko-corp.co.jp/qcs/ja/shor.html